LeetCode 17 Letter Combinations of a Phone Number：電話號碼字母組合

題目翻譯

給定數字字串（2-9），返回所有可能的字母組合。數字到字母映射同電話鍵盤。輸入 "23" → 輸出 ["ad","ae","af","bd","be","bf","cd","ce","cf"]。順序不限。

解題思路

經典回溯/遞歸問題。對每個數字遍歷對應字母，遞歸處理剩餘數字，直到處理完所有數字將組合加入結果。因輸入長度不定，遞歸比巢狀迴圈更適合。

C# 實現

public class Solution {
    IList<string> list = new List<string> { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    public IList<string> LetterCombinations(string digits) {
        IList<string> result = new List<string>();
        if (digits.Length == 0) return result;
        if (digits.Length == 1) {
            foreach (var c in list[digits[0] - '2']) result.Add(c.ToString());
            return result;
        }
        int count = 0;
        IList<string> temp = LetterCombinations(digits.Substring(1));
        foreach (var c in list[digits[0] - '2'])
            foreach (var rest in temp)
                result.Insert(count++, c + rest);
        return result;
    }
}

C++ 實現（更高效）

class Solution {
    string dic[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        if (digits.empty()) return ans;
        string tmp(digits.size(), ' ');
        dfs(tmp, 0, digits.size(), ans, digits);
        return ans;
    }
    void dfs(string &tmp, int dep, int n, vector<string> &ans, string &digits) {
        if (dep == n) { ans.push_back(tmp); return; }
        for (char c : dic[digits[dep] - '0']) {
            tmp[dep] = c;
            dfs(tmp, dep + 1, n, ans, digits);
        }
    }
};

複雜度

• 時間：O(4^N)，N 為數字長度（最多 4 字母）。
• 空間：O(N) 遞歸棧 + O(4^N) 結果。