LeetCode Letter Combinations of a Phone Number：DFS 回溯生成所有組合

題目回顧

給定一個只包含數字 2-9 的字符串，返回所有可能的字母組合（按電話鍵盤映射）。例如 "23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"]。

映射表

2: abc   3: def   4: ghi   5: jkl
6: mno   7: pqrs  8: tuv   9: wxyz

核心思路：DFS 回溯

這是經典的組合生成問題，每個數字對應一組候選字母，依次選取並遞歸處理下一位。

遞歸框架

• 狀態：當前處理到第 index 個數字，已構建的前綴 path
• 選擇：遍歷 digits[index] 對應的所有字母
• 終止條件：index == digits.length，將 path 加入結果
• 回溯：撤銷最後加入的字母（或傳遞新字符串副本）

C++ 參考實現

class Solution {
    vector result;
    const vector keypad = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
public:
    vector letterCombinations(string digits) {
        if (digits.empty()) return result;
        dfs(digits, 0, "");
        return result;
    }
    
private:
    void dfs(const string& digits, int index, string path) {
        if (index == digits.size()) {
            result.push_back(path);
            return;
        }
        string letters = keypad[digits[index] - '0'];
        for (char c : letters) {
            dfs(digits, index + 1, path + c); // 傳遞副本，無需顯式回溯
        }
    }
};

Python 簡潔版

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        keypad = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        res = []
        def dfs(i, path):
            if i == len(digits):
                res.append(path)
                return
            for c in keypad[ord(digits[i]) - ord('0')]:
                dfs(i + 1, path + c)
        dfs(0, "")
        return res

複雜度分析

• 時間：O(4ⁿ × n)，最坏情況每位 4 個字母（7/9），共 n 位，每次拷貝字符串 O(n)
• 空間：O(n) 遞歸棧 + O(4ⁿ × n) 結果存儲

優化方向

1. 避免字符串拷貝：使用可變容器（如 vector 或 string + push_back/pop_back）
2. 迭代法：用隊列或逐位擴展結果集，避免遞歸開銷

迭代法示例

vector letterCombinations(string digits) {
    if (digits.empty()) return {};
    vector res = {""};
    for (char d : digits) {
        vector tmp;
        for (const string& s : res) {
            for (char c : keypad[d - '0']) {
                tmp.push_back(s + c);
            }
        }
        res.swap(tmp);
    }
    return res;
}

總結

電話號碼字母組合是 DFS 回溯的入門級應用。關鍵在於：

• 建立正確的數字→字母映射
• 設計清晰的遞歸狀態與終止條件
• 理解組合爆炸的複雜度本質，面試中說明優化思路即可