Pythonで解く！電話番号からすべての文字の組み合わせを生成する方法

2〜9までの数字を含む文字列が与えられたとき、その番号が表しうるすべての文字の組み合わせを返すことを考えます。以下は、電話のダイヤルボタンと同じように、各数字に割り当てられた文字のマッピングです。なお、「1」はどの文字にも対応しない点に注意してください。

たとえば、入力として「23」が与えられた場合、生成される可能性のある文字列は次のようになります。

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

解法のアプローチ

この問題は、再帰的なバックトラッキングを用いることで効率的に解けます。手順は以下の通りです。

• 問題を再帰的に解決するための solve メソッドを定義します。
• solve メソッドは、digits（数字列）、characters（マッピング）、result（結果リスト）、current_string（現在構築中の文字列）、current_level（現在処理中の桁位置）を引数として受け取ります。
• current_level が digits の長さと等しくなったら、1つの組み合わせが完成したことになるため、current_string を result に追加して処理を終了します。
• それ以外の場合は、characters[digits[current_level]] に含まれる各文字 i について、solve(digits, characters, result, current_string + i, current_level + 1) を再帰的に呼び出します。

メイン関数の流れ

• digits の長さが0の場合は、空のリストを返します。
• 数字と対応する文字列を保持する辞書（マップ）を定義します。
• 結果を格納する空のリスト result を用意します。
• solve(digits, characters, result, "", 0) を呼び出して探索を開始します。

実装例（Python）

理解を深めるために、実際のコードを見てみましょう。

class Solution(object):
    def letterCombinations(self, digits):
        if len(digits) == 0:
            return []
        characters = {2:"abc",3:"def",4:"ghi",5:"jkl",6:"mno",7:"pqrs",8:"tuv",9:"wxyz"}
        result = []
        self.solve(digits,characters,result)
        return result
    def solve(self, digits, characters, result, current_string="",current_level = 0):
        if current_level == len(digits):
            result.append(current_string)
            return
        for i in characters[int(digits[current_level])]:
            self.solve(digits,characters,result,current_string+i,current_level+1)
ob1 = Solution()
print(ob1.letterCombinations("37"))

入力

"37"

出力

["dp","dq","dr","ds","ep","eq","er","es","fp","fq","fr","fs"]

このように、再帰とバックトラッキングを組み合わせることで、数字列に対応するすべての文字の組み合わせを漏れなく生成できます。計算量は入力の長さに対して指数的に増加しますが、電話番号のような短い入力であれば十分に高速に動作します。