Letter Combinations of a Phone Number
電話のキーパッドでは、2から9までの各数字にいくつかの文字が割り当てられています。2はabc、3はdef、4はghi、5はjkl、6はmno、7はpqrs、8はtuv、9はwxyzです。
文字列digitsが与えられます。数字の順序を保ちながら、各数字に対して1つの文字を選ぶと、キーで入力できる文字列が1つ得られます。そのような文字列をすべて辞書順に並べて返してください。"23"の場合、"ad"から"cf"までの9つの文字列になります。
関数
- digitsstring
- 押された数字（それぞれ2から9）
- 戻り値string-array
- キーで入力できるすべての文字列を辞書順に
制約
1 ≤ digits.length ≤ 4-
digitsの各文字は、2から9までの数字です。 - 答えは最大で
44 = 256個の文字列を含みます。
例
- 入力
- digits = "23"
- 出力
- ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
- 説明
- 2は
a、b、cを、3はd、e、fを提供します。それぞれの1文字目は2文字目のそれぞれと組み合わさるので、文字列は3 × 3 = 9個あり、1文字目の変化を最も遅くして列挙すると、並べ替えられた状態を保てます。
- 入力
- digits = "7"
- 出力
- ["p", "q", "r", "s"]
- 説明
- 1桁の数字では、その文字のそれぞれが答え全体になります。7は4文字を持つ2つのキーのうちの1つなので、答えは4つの文字列になります。
- 入力
- digits = "94"
- 出力
- ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
- 説明
- 9は4文字で、4は3文字なので、文字列は全部で4 × 3 = 12個あります。
wで始まる3つの文字列は、xで始まる最初の文字列より前に来ます。
提出時に隠しテスト+14件
発展問題
辞書に載っている実在の単語の組み合わせだけが欲しいとします。まずすべての 4^n 文字列を作らずに済ませるには、どうすればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
選択肢を木として描きます。第1階層では最初の桁の文字を選び、第2階層では2番目の桁の文字を選び、以下同様に続きます。根から葉までの経路は何を綴っていますか？
各葉は1つの答えであり、各答えは1つの葉です。木を深さ優先でたどり、各キーの文字を左から右へ試していくと、葉に辞書順で出会います。
増えていく文字列を1つ保持します。位置
iで、digits[i]の各文字を順に追加し、位置i+1に進んでから、その文字を再び削除します。iがdigitsの末尾に達したら、文字列のコピーを保存します。
解説
ここでは何も省略できません。答え自体に最大で4^n個の文字列が含まれるため、正しい解法はどれも、それらを書き出すだけで少なくとも同じだけの作業を必要とします。この問題で試されているのは、選択肢の集合を、漏れや重複なく体系的に生成できるかどうかです。これが、最も単純な形のバックトラッキングです。各桁に1つのレベルを持つ決定木を深さ優先でたどり、各葉が1つの答えになります。
文字列を1桁ずつ組み立てる
考え方
答えを1桁ずつ作ります。まず、空文字列を1つ含むリストから始めます。"23"の場合、数字の2によってa、b、cになります。次に数字の3によって、それぞれにd、e、fを追加し、長さ2の文字列が9個できます。最後の数字まで処理すると、リストにはすべての答えが含まれます。
並び順は何もしなくてもソート済みになります。ある数字を処理する前にリストがソートされているとします。接頭辞はその順序のまま拡張し、各接頭辞にはキーの文字を左から右へ追加します。先に来る接頭辞を持つ文字列は引き続き先に来ます。また、同じ接頭辞を持つ2つの文字列は新しい文字の順、つまり辞書順に並びます。
コストは答えのサイズによって決まります。n桁の場合、最後のリストには長さnの文字列が最大4^n個含まれ、それ以前のリストに含まれる文字列の合計は、その半分以下です。しかも、それらはすべてより短い文字列です。欠点はメモリ使用量です。1つの段階を作る間、捨てることになる短い接頭辞もすべて含め、前の段階全体も保持されます。
アルゴリズム
combos = [""]（空のプレフィックス）から始めます。- 各数字について、新しいリストを作成します。
combos内の各プレフィックスと、その数字のキーにある各文字について、prefix + letterを追加します。 combosを新しいリストに置き換えます。- 最後の数字の処理後、
combosを返します。
KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
def letterCombinations(digits):
combos = [""] # every prefix built so far; one empty prefix to start
for digit in digits:
# Each old prefix grows by each letter of this digit, in order.
combos = [prefix + letter for prefix in combos for letter in KEYPAD[digit]]
return combos決定木のバックトラッキング
考え方
答えを決定木として考えてみましょう。根は空文字列です。"23"の場合、子は3つあり、それぞれ2の文字に対応するa、b、cです。それぞれの子にも、3の各文字に対応する子が3つずつあります。木は数字ごとに1段あり、9つの葉であるadからcfまでが、答えそのものです。
バックトラッキングでは、1つのバッファーpathを使って、その木を深さ優先でたどります。レベルiでは、digits[i]の文字を追加して選択し、i+1で再帰呼び出しをしてその下をすべて探索し、文字を削除して選択を取り消します。この取り消しによって、1つのバッファーで木全体を扱えます。ad、ae、afを保存したあと、末尾から文字を取り除くとpathはaに戻り、次に空文字列に戻るので、bに進む準備ができます。iがdigitsの長さと等しくなると、バッファーには答えがすべて入っているので、そのコピーを保存します。
各レベルで左から右へ文字を試すと、葉は辞書順に訪れるため、出力をソートする必要はありません。この問題ではすべての分岐が答えにたどり着くので、枝刈りするものはありません。木は深さがわずか4で、葉の数は最大256です。答えを書き出す処理には、引き続きO(4^n · n)の時間がかかりますが、追加メモリはバッファーと呼び出しスタックのO(n)であり、接頭辞の階層全体を保持する必要はありません。同じ選択、探索、取り消しのループで、部分集合、順列、組み合わせの合計、単語検索を解けます。
アルゴリズム
- 空の
pathと空のresultを用意します。 backtrack(i)を定義します。iがdigitsの長さと等しい場合、pathのコピーを保存して戻ります。- それ以外の場合、
digits[i]のキーにある各文字について、順番に、pathに追加し、backtrack(i+1)を呼び出してから、その文字を削除します。 backtrack(0)を呼び出し、resultを返します。
KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
def letterCombinations(digits):
result = []
path = [] # the letters chosen so far, one per digit
def backtrack(i):
if i == len(digits):
# Every digit has a letter: this leaf is one finished string.
result.append("".join(path))
return
for letter in KEYPAD[digits[i]]:
path.append(letter) # choose
backtrack(i + 1) # explore the digits after this one
path.pop() # undo, so the next letter can take its place
backtrack(0)
return result
落とし穴と境界ケース
探索自体は短いため、バグの大半は KEYPAD または共有バッファに起因します。
- 各キーに文字が3つあると思い込む。7は
pqrs、9はwxyzなので、アルファベットの(d-2)*3の位置から3文字取ると、7のsが抜け、8はtではなくsから始まってしまいます。KEYPADを表に書き出しましょう。 - 取り消し処理を忘れる。再帰呼び出しの後に文字を削除しないと、
pathが伸び続け、"23"に対する2つ目の答えがaeではなくadeになります。 - コピーではなくバッファ自体を保存する。Pythonでは、
result.append(path)は同じリストを9回保存し、最後には空になってしまいます。保存するときに、新しい文字列に結合しましょう。 - 順序が崩れる。キーの文字を右から左に試したり、反復処理版でスタックから文字列を伸ばしたりすると、問題が求めるソート順とは異なる順序で答えが得られます。
- 数字の文字列が数値として読み込まれる。PHPやRのような動的型付け言語では、
"23"が数値の23として渡されることがあります。文字をインデックスで参照する前に、テキストに変換しましょう。
よくある質問4
電話番号の文字の組み合わせの時間計算量はどれくらいですか？
n 桁の場合、計算量は O(4^n · n) です。すべての桁が 7 または 9 の場合、文字列は 4^n 個でき、それぞれを書き出すのに n ステップかかるためです。キーが 3 文字のみの場合は O(3^n · n) です。これより効率のよい解法はありません。出力のサイズがこの大きさだからです。バックトラッキングでは、出力とは別に O(n) の追加領域が必要です。
再帰を使わずに Letter Combinations を解けますか？
はい。答えをレベルごとに構築します。空の文字列1つから始め、各数字について、これまでにあるすべての文字列に、そのキーに対応する各文字を追加していきます。処理量は同じで、同じ木を深さ優先ではなく幅優先でたどります。メモリには接頭辞のレベル全体を保持しますが、再帰で必要なのは数字の個数分の深さのスタックだけです。
バックトラッキングでは、なぜ組み合わせがソートされた順序で返されるのでしょうか？
すべての答えの長さは同じで、深さ優先探索では、最初の階層でaではなくbを選ぶ前に、aで始まるすべての文字列を最後までたどります。各階層でも同じことが当てはまり、それぞれのキーの文字を左から右へ試す限り、これは辞書順そのものなので、ソートは必要ありません。
数字の0と1はどうでしょうか？
電話のキーパッドでは、0と1には文字が割り当てられておらず、この問題のバージョンでは2から9だけを使います。もし0や1が現れる可能性があるなら、選べる文字がないため、その数字をスキップするのか、答えを空にするのかを決める必要があります。面接では、コードを書く前にどちらが求められているか確認しましょう。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def letterCombinations(digits):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
digits = "23"
期待値
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]