問題概要

数字文字列（2-9）が与えられた時、電話のキーパッドのように各数字に対応する文字の全ての組み合わせを生成する問題です。

2
ABC
3
DEF
4
GHI
5
JKL
6
MNO
7
PQRS
8
TUV
9
WXYZ

例

  • Input: "23" → Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
  • Input: "" → Output: []
  • Input: "2" → Output: ["a","b","c"]

アルゴリズム解説：バックトラッキング

この問題はバックトラッキング（DFS）を使用して解決します。各桁に対して可能な文字を順次試し、全ての組み合わせを生成します。

実装コード

Python - Solution 
from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        """
        バックトラッキングで電話番号の文字組み合わせを生成

        時間計算量: O(3^N × 4^M)
        空間計算量: O(組み合わせ数 + 再帰スタック)
        """
        if not digits:
            return []

        # 数字と文字のマッピング
        phone_map = {
            "2": "abc", "3": "def", "4": "ghi",
            "5": "jkl", "6": "mno", "7": "pqrs",
            "8": "tuv", "9": "wxyz"
        }

        result = []

        def backtrack(index: int, path: str) -> None:
            """
            再帰的に文字列の組み合わせを構築

            Args:
                index: digits内の現在の桁位置
                path: 現在までの組み合わせ文字列
            """
            # ベースケース：全桁処理完了
            if index == len(digits):
                result.append(path)
                return

            # 現在の数字に対応する文字で探索
            current_digit = digits[index]
            for letter in phone_map[current_digit]:
                backtrack(index + 1, path + letter)

        backtrack(0, "")
        return result

インタラクティブデモ

数字を入力して実行ボタンを押してください

ステップバイステップ解説

digits = "23" の場合の実行過程を詳しく見てみましょう。

1 初期状態： backtrack(0, "") を呼び出し
index=0, path="", digits[0]='2' → letters="abc"
2 1段目探索： 'a' を選択
backtrack(1, "a") を呼び出し、digits[1]='3' → letters="def"
3 2段目探索： 'd' を選択
backtrack(2, "ad") → index==len(digits) → result.append("ad")
4 バックトラック： 'e' を選択
backtrack(2, "ae") → result.append("ae")
5 バックトラック： 'f' を選択
backtrack(2, "af") → result.append("af")
6 次の分岐： 'b' を選択
backtrack(1, "b") → "bd", "be", "bf" を生成
7 最後の分岐： 'c' を選択
backtrack(1, "c") → "cd", "ce", "cf" を生成
8 完了： 全組み合わせ生成完了
result = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

探索木の可視化

root: ""
a
b
c
ad
ae
af
bd
be
bf
cd
ce
cf

計算量解析

時間計算量

O(3^N × 4^M)

N: 3文字キーの個数
M: 4文字キーの個数

空間計算量

O(R + D)

R: 結果の組み合わせ数
D: 再帰の深さ

具体例での計算量

入力 組み合わせ数 計算過程
"2" 3 3^1 = 3
"23" 9 3 × 3 = 9
"279" 48 3 × 4 × 4 = 48
"2379" 144 3 × 3 × 4 × 4 = 144

重要なポイント

DFS探索

深度優先探索で全ての組み合わせを体系的に生成

バックトラッキング

各選択肢を試した後、前の状態に戻って次の選択肢を探索

再帰構造

問題を小さな部分問題に分解して解決

指数時間

組み合わせの性質上、指数的な時間計算量が発生

実装のベストプラクティス

最適化のポイント

  • 早期終了： 空文字列の場合は即座に空リストを返却
  • メモリ効率： 文字列結合を最小限に抑制
  • 型安全性： 適切な型ヒントの使用
  • 可読性： 明確な変数名とコメント

エラーハンドリング

Python - Enhanced Version 
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # 入力検証
        if not digits or not digits.isdigit():
            return []

        # 無効な数字をチェック
        if any(d in '01' for d in digits):
            raise ValueError("Invalid digit: only 2-9 are allowed")

        phone_map = {
            "2": "abc", "3": "def", "4": "ghi",
            "5": "jkl", "6": "mno", "7": "pqrs",
            "8": "tuv", "9": "wxyz"
        }

        result = []

        def backtrack(index: int, path: str) -> None:
            if index == len(digits):
                result.append(path)
                return

            current_digit = digits[index]
            if current_digit not in phone_map:
                return  # スキップ

            for letter in phone_map[current_digit]:
                backtrack(index + 1, path + letter)

        backtrack(0, "")
        return result

代替実装方法

1. 反復的アプローチ（BFS）

Python - Iterative BFS 
def letterCombinations_iterative(self, digits: str) -> List[str]:
    if not digits:
        return []

    phone_map = {
        "2": "abc", "3": "def", "4": "ghi",
        "5": "jkl", "6": "mno", "7": "pqrs",
        "8": "tuv", "9": "wxyz"
    }

    result = [""]

    for digit in digits:
        temp = []
        for combination in result:
            for letter in phone_map[digit]:
                temp.append(combination + letter)
        result = temp

    return result

2. 関数型プログラミングスタイル

Python - Functional Style 
from itertools import product

def letterCombinations_functional(self, digits: str) -> List[str]:
    if not digits:
        return []

    phone_map = {
        "2": "abc", "3": "def", "4": "ghi",
        "5": "jkl", "6": "mno", "7": "pqrs",
        "8": "tuv", "9": "wxyz"
    }

    # 各数字に対応する文字列のリストを作成
    letter_groups = [phone_map[digit] for digit in digits]

    # 直積を計算して組み合わせ生成
    return [''.join(combination) for combination in product(*letter_groups)]