問題
原文
Given a string containing digits from
2-9inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Example 2:
Example 3:
Constraints:
0 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
内容
2~9の数字を含む文字列が与えられます。
表すことができる全ての組み合わせを順序を問わず返してください。
数字と文字列の対応(携帯電話のボタンのような)は以下(問題文の画像)の通りです。
注意：1はどの文字列にも対応していません。
制約
・digitsの長さは0~4の範囲
→入力されるdigitsがない場合の考慮が必要
→digitsは4までなので、1つの組み合わせでの最大は4*4*4*4=256個になりそう
※7,9は文字列が4つある
・digits[i]は2~9の範囲
※正しくない可能性があります。
解答
解答1：Python, backtracking
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
class Solution: def letterCombinations(self, digits: str) -> List[str]: #キーごとの文字列を準備 digits_to_letters = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz", } #解答用のリスト answer = [] # combination = "" #インデックス用変数 index = 0 #digitに入力値を代入 digit = digits #入力値が空リストなら空リストを返す if not digit: return [] #入力値が空でない場合backtrackメソッドを呼び出して、answerを返す else: self.backtrack(combination, digit, answer, digits_to_letters) return answer def backtrack(self, combination, digit, answer, digits_to_letters): #digitに次の値がなければanswerにcombinationを追加して終了 if not digit: answer.append(combination) return #digitに次の値があれば、for文で組み合わせを作る else: #forはキーごとの全文字を走査する #digits_to_letters[digit[0]]は携帯のキーの1文字目(a,d,g,j・・・) #digits[0]は234など押下されたキーの1文字目 for letter in digits_to_letters[digit[0]]: #combinationは初めはから。1回呼び出すごとにletter(各キー)を1文字ずつ後ろに付け加える #digitは2文字目以降のみにする→digit[1:] self.backtrack(combination+letter, digit[1:], answer, digits_to_letters) #print(answer,"answer") """ ・digitsが1文字だけの場合、例えば2のみなら、for文が2に対して1回実行されて、[a,b,c]の中から1文字ずつの組合せを作る 2文字目がないので、answerにa,b,cが1文字ずつ追加され、再帰呼び出し終了 ・digitsが2文字の場合、例えば23なら、for文が2と3に対して合計2回実行されて、[a,b,c]と[d,e,f]の中から2文字ずつの組合せを作る 2文字目まではあるのでad,ae,af,bd,be,bfの順にanswerに追加。 3文字目はないので、2文字目までの組み合わせを作ったら再帰呼び出し終了 ・digitsが3文字の場合、例えば234なら、for文が2,3,4に対して合計3回実行。 [a,b,c],[d,e,f],[g,h,i]の中から3文字ずつの組合せを作る 最初に、2の1文字目、3の1文字目、4の1文字目までcombinationに加える。 4文字目はないので空が返され、answerにcombination→2の1文字目、3の1文字目、4の1文字目を加える 次に、2の1文字目、3の1文字目、4の2文字目までcombinationに加える。 4文字目はないので空が返され、answerにcombination→2の1文字目、3の1文字目、4の2文字目を加える 次に、2の1文字目、3の1文字目、4の3文字目までcombinationに加える。 4文字目はないので空が返され、answerにcombination→2の1文字目、3の1文字目、4の3文字目を加える 次に、2の1文字目、3の2文字目、4の1文字目までcombinationに加える。 4文字目はないので空が返され、answerにcombination→2の1文字目、3の2文字目、4の1文字目を加える 同じことを繰り返す """ |
・digits=23の場合のイメージ
backtrack(“”,23): ※関数letterCombinationsでの呼び出し
※以降は全て関数backtrack内での動作
for letter in “abc”:
➀backtrack(a,3):
→for letter in “def”:
→→backtrack(ad,[]):
→→→answer = (ad)
→→backtrack(ae,[]):
→→→answer = ad,ae)
→→backtrack(ae,[]):
→→→answer = (ad,ae,af)
②backtrack(b,3):
→for letter in “def”:
→→backtrack(bd,[]):
→→→answer = (ad,ae,af,bd)
→→backtrack(be,[]):
→→→answer = (ad,ae,af,bd,be)
→→backtrack(bf,[]):
→→→answer = (ad,ae,af,bd,be,bf)
③backtrack(c,3):
→for letter in “def2:
→→backtrack(cd,[]):
→→→answer = (ad,ae,af,bd,be,bf,cd)
→→backtrack(ce,[]):
→→→answer = (ad,ae,af,bd,be,bf,cd,ce)
→→backtrack(cf,[]):
→→→answer = (ad,ae,af,bd,be,bf,cd,ce,cf)
メモ・参考・感想
コメント