Pythonで電話のキーパッドから生成されるすべての文字列の組み合わせを求めるプログラム

ここでは、2〜9の数字のみを含む文字列が与えられたとき、その数字列から生成されうるすべての文字の組み合わせを求める方法を解説します。数字と文字の対応関係は、一般的な電話機のテンキーと同じです。なお、「1」にはいくつかの記号が割り当てられていますが、英字は割り当てられていません。

たとえば、入力として「49」が与えられた場合、出力される可能性のある文字列は次の12通りになります。

['gw', 'gx', 'gy', 'gz', 'hw', 'hx', 'hy', 'hz', 'iw', 'ix', 'iy', 'iz']

解法のアプローチ

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

• 再帰的に処理を行うための 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) を呼び出して探索を開始します。

実装例

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

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("49"))

入力

"49"

出力

['gw', 'gx', 'gy', 'gz', 'hw', 'hx', 'hy', 'hz', 'iw', 'ix', 'iy', 'iz']

計算量について

各桁に対応する文字数を m、数字列の長さを n とすると、生成される組み合わせの総数は最大で mⁿ となるため、時間計算量・空間計算量はいずれも O(mⁿ) になります。これは、すべての組み合わせを出力する必要がある問題において理論上の下限でもあります。