Letter Combinations of a Phone Number

題目描述

給定一個包含數字 2-9 的字串，回傳所有可能的字母組合。數字到字母的對應和電話鍵盤一樣。

輸入：digits = "23"
輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

輸入：digits = ""
輸出：[]

解題思路

建立對照表

用 HashMap 建立數字到字母的映射：2→abc, 3→def, 4→ghi, 5→jkl, 6→mno, 7→pqrs, 8→tuv, 9→wxyz

回溯起點

呼叫 backtrack(idx=0, path=[])，從第一個數字開始、路徑為空

枚舉字母

查表取 digits[idx] 對應的字母集合，用 for 迴圈逐一嘗試每個字母

遞迴下一層

將選中字母加入 path，遞迴呼叫 backtrack(idx+1, path)。回傳後 pop 掉最後一個字母（回溯）

收集結果

當 idx 等於 digits.length 時，path 已有完整組合，複製一份加入結果集

程式碼

C#

csharp

public class Solution {
    public IList<string> LetterCombinations(string digits) {
        if (string.IsNullOrEmpty(digits)) return new List<string>();
        
        var map = new Dictionary<char, string> {
            {'2',"abc"}, {'3',"def"}, {'4',"ghi"}, {'5',"jkl"},
            {'6',"mno"}, {'7',"pqrs"}, {'8',"tuv"}, {'9',"wxyz"}
        };
        var result = new List<string>();
        Backtrack(digits, 0, new char[digits.Length], map, result);
        return result;
    }
    
    private void Backtrack(string digits, int idx, char[] path,
                           Dictionary<char, string> map, List<string> result) {
        if (idx == digits.Length) {
            result.Add(new string(path));
            return;
        }
        foreach (char c in map[digits[idx]]) {
            path[idx] = c;
            Backtrack(digits, idx + 1, path, map, result);
        }
    }
}

TypeScript

typescript

function letterCombinations(digits: string): string[] {
    if (!digits) return [];
    
    const map: Record<string, string> = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    };
    const result: string[] = [];
    
    function backtrack(idx: number, path: string) {
        if (idx === digits.length) {
            result.push(path);
            return;
        }
        for (const c of map[digits[idx]]) {
            backtrack(idx + 1, path + c);
        }
    }
    
    backtrack(0, '');
    return result;
}

Python

python

def letterCombinations(digits: str) -> list[str]:
    if not digits:
        return []
    
    phone = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    result = []
    
    def backtrack(idx: int, path: list[str]):
        if idx == len(digits):
            result.append(''.join(path))
            return
        for char in phone[digits[idx]]:
            path.append(char)
            backtrack(idx + 1, path)
            path.pop()  # 回溯：撤銷選擇
    
    backtrack(0, [])
    return result

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(4^n) | O(n) |

其中 n = digits 長度，4 是每個數字最多對應的字母數（如 7→pqrs）。

Time：最壞情況所有數字都對應 4 個字母，組合樹有 4^n 個葉節點，每個葉節點生成一個長度為 n 的字串
Space：遞迴深度為 n（digits 長度），不計輸出的話是 O(n)

圖解

開始 (digits=23)

2→a→

3→d→

3→d...→

→

樹狀圖展示了回溯法的搜尋過程：第一層枚舉第一個數字對應的所有字母，第二層枚舉第二個數字的字母。每條從根到葉的路徑就是一個完整組合，digits="23" 共產生 3×3=9 種組合。

進階觀點

💡面試追問

能用 BFS 代替回溯嗎？ 可以。用 queue 存放當前所有部分組合，每次取出一個、對下一個數字的每個字母生成新組合放回 queue。優點是不用遞迴，缺點是 queue 中同時存放大量中間結果，空間消耗更大。
結果天然是字典序嗎？ 是的，只要對照表中每個數字的字母按 a-z 排列（本來就是），回溯的枚舉順序就保證結果按字典序產生。
T9 輸入法的原理？ 就是這題的核心：使用者按數字序列，系統枚舉所有可能的字母組合，再與字典匹配過濾出合法單字。現代實作會加上頻率排序和預測模型。

邊界情況

digits 為空字串：直接回傳空陣列，不進入回溯
digits 只有一個字元：結果就是該數字對應的字母列表，如 "7" → ["p","q","r","s"]
digits 很長（如長度 10）：最多產生 4^10 = 1,048,576 個組合，仍在可接受範圍內但要注意記憶體

理解測驗

🤔 如果 digits = "79"，總共會產生幾種組合？

🤔 回溯法中「撤銷選擇」這一步的作用是什麼？