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つできます。そのような文字列をすべて辞書順に並べて返してください。
関数
- 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で始まる最初の文字列より前に来ます。
発展問題
辞書に載っている実在の単語の組み合わせだけが欲しいとします。すべての 4^n の文字列を先に作らずに済ませるには、どうすればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
選択肢を木として描きます。第1レベルでは最初の桁の文字を選び、第2レベルでは2番目の桁の文字を選び、以下同様に続きます。根から葉までの経路は何を綴っていますか？
各葉は1つの答えであり、各答えは1つの葉です。木を深さ優先でたどり、各キーの文字を左から順に試すと、葉に辞書順で出会います。
1つの文字列を伸ばし続けます。位置
iで、digits[i]の各文字を順に追加し、位置i+1に進んでから、その文字を再び削除します。iがdigitsの末尾に達したら、文字列のコピーを保存します。
解説
答えは最大で 4^n 個の文字列を含むため、すべての解法で、それらを書き出すのに少なくともそれだけの作業が必要です。重要なのは、選択肢を漏れや重複なく、それぞれ一度ずつ生成することです。これは、数字ごとに1つの階層があり、各葉が答えとなる決定木をバックトラッキングすることです。
文字列を1桁ずつ組み立てる
考え方
空文字列を1つ含むリストから始め、1桁ずつ拡張します。"23"の場合、数字の2によって a、b、cになり、3によってそれぞれに d、e、fが追加され、9個の文字列ができます。
順序はソートされたままです。数字を処理する前にリストがソートされていれば、その順序で各接頭辞を拡張し、それぞれの接頭辞にはキーに対応する文字を左から順に追加します。先にあった接頭辞はそのまま先に並び、同じ接頭辞同士は新しい文字の順に並びます。
処理量は答えのサイズに比例しますが、各段階を構築している間は、前の段階の全体もメモリに残ります。
アルゴリズム
combos = [""]（空の接頭辞1つ）から始めます。- 各数字について、新しいリストを作ります。
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決定木を使ったバックトラッキング
考え方
答えは決定木の葉です。根は空文字列で、各レベルでは次の数字の1文字が追加されます。"23"の場合、根にはa、b、cの子があり、それぞれにd、e、fの子があります。
1つのバッファpathを使って、深さ優先でたどります。レベルiでは、digits[i]の文字を追加して選択し、i+1で再帰して探索し、その文字を削除して元に戻します。元に戻すことで、1つのバッファで木全体を処理できます。ad、ae、afの後でポップすると、pathはaに戻り、次に空文字列に戻るので、bの準備が整います。iがdigitsの末尾に達したら、コピーを保存します。
時間計算量は依然として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
落とし穴と境界ケース
- すべてのキーに3文字ずつあると仮定する。アルファベットのインデックス
(d-2)*3から3文字を取ると、7からsが抜け、8がsから始まってしまいます。キーパッドを表に書き出しましょう。 - 元に戻す処理を忘れる。
pathが増え続け、"23"に対する2番目の答えがaeではなくadeになります。 - コピーではなくバッファを保存する。Pythonでは、
result.append(path)は同じリストを9回保存するため、最後には空になっています。 - キーの文字を右から左に試す、または反復版でスタックから文字列を伸ばす。どちらもソート順を崩します。
- PHPとRでは、
"23"が数値の23として渡されることがあります。文字にインデックスを付ける前に、テキストに変換しましょう。
よくある質問3
電話番号の文字の組み合わせの時間計算量はどれくらいですか？
n 桁の場合は O(4^n · n) です。各桁が 7 または 9 のとき、4^n 個の文字列があり、それぞれを書くのに n ステップかかります。これが出力のサイズなので、これより効率のよい解法はありません。バックトラッキングでは、出力以外に O(n) の追加領域が必要です。
バックトラッキングでは、なぜ組み合わせがソートされた順序で返されるのでしょうか？
すべての答えの長さは同じで、深さ優先探索では、aで始まるすべての文字列を処理し終えてからbを選びます。各キーの文字を左から右へ試す限り、これはどの階層でも同じです。これは辞書順なので、ソートは不要です。
数字の0と1はどうでしょうか？
電話のキーパッドでは、0と1には文字が割り当てられておらず、このバージョンでは2から9のみを使用します。0や1が現れる可能性がある場合、そのような数字をスキップするのか、答えを空にするのかを決める必要があります。面接では、どちらが求められているか確認しましょう。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def letterCombinations(digits):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
digits = "23"
期待される出力
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]