电话号码的字母组合 图解题解

这道题到底在问什么

digits

"23"

映射

2→abc, 3→def

输出

ad ae af bd be bf cd ce cf

先想最直接的笨办法

两位写两层 for、五位写五层……可 digits 的长度是变量，层数不固定，嵌套循环根本写不出来，这是暴力解卡死的地方。（动画第 3 步）

最优解：一步一步想明白

1. 3两位写两层 for、五位写五层……可 digits 的长度是变量，层数不固定，嵌套循环根本写不出来，这是暴力解卡死的地方。
2. 4转折：用递归替掉「不定层循环」。先建好键盘映射 {2:abc, 3:def, ...}；递归到第 i 位时，枚举 digits[i] 对应的几个字母，每选一个就 i+1 去定下一位；i 走到末尾说明每位都定好了，把 path 拼成串收进结果，然后撤销刚才那个字母，回上层换下一个。选→递归→撤销，三步循环。
3. 5path=[a]，去定第 2 位从第 1 位开始，digits[0]="2" 的候选是 a/b/c。先选 a，path=["a"]，还没到末尾，i+1 进入第 2 位。
4. 6i 到末尾，收下 "ad"切到第 2 位：候选换成 digits[1]="3" 的 d/e/f（格子里的字母随之换成 d/e/f）。选 d，path=["a","d"]，i 已到末尾——两位都定完，拼成 "ad" 收进结果。
5. 7path 退回 [a]，再选 e负例/回溯动作：把刚选的 d 弹出，path 退回 ["a"]，d 重新变回「可选」。不撤销的话第 2 位会越积越长、串到下一个字母里。撤销后在第 2 位改选 e，收下 "ae"。
6. 8a 打头的全收齐同样撤销 e、改选 f，收下 "af"。第 2 位的 d/e/f 都和 a 配过了，a 打头的三种全齐。接着把第 2 位整个撤销、退回第 1 位换头。
7. 9path=[b]，再下探第 2 位回到第 1 位，候选又变回 a/b/c。a 撤销后改选 b，path=["b"]，再 i+1 去定第 2 位。流程和 a 打头时一模一样。
8. 10收下 "bd"第 2 位又切到 d/e/f。选 d，path=["b","d"]，到末尾，收下 "bd"。接着同样撤销换 e、换 f，能收 "be"、"bf"。
9. 11be / bf 也收下b 配完 d/e/f，收下 "be"、"bf"。b 打头的三种也全了。再撤销退回第 1 位，最后把头换成 c。
10. 123×3 = 9 种全部收齐c 打头同样配 d/e/f，收下 "cd"、"ce"、"cf"。最终 9 种组合不重不漏全部收齐，正好是 3×3。
11. 15「多个位置、每个位置有几种选法、求全部搭配（笛卡尔积）」的通用解法：一层递归管一位，到底就收。位数不定时，它替你写出「层数随输入变化」的循环。
12. 20把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def letterCombinations(self, digits):
        if not digits:
            return []
        mp = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        ans = []
        def backtrack(i, path):
            if i == len(digits):
                ans.append(''.join(path))
                return
            for ch in mp[digits[i]]:
                path.append(ch)
                backtrack(i + 1, path)
                path.pop()
        backtrack(0, [])
        return ans

class Solution {
public:
    vector<string> ans;
    string digs;
    vector<string> mp = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    void backtrack(int i, string& path) {
        if (i == digs.size()) { ans.push_back(path); return; }
        for (char ch : mp[digs[i] - 48]) {          // digs[i]-'0': 该数字对应字母
            path.push_back(ch);
            backtrack(i + 1, path);                 // 下探到下一位
            path.pop_back();                         // 撤销
        }
    }
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        digs = digits; string path;
        backtrack(0, path);
        return ans;
    }
};

class Solution {
    String[] mp = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> ans = new ArrayList<>();
    String digs;
    void backtrack(int i, StringBuilder path) {
        if (i == digs.length()) { ans.add(path.toString()); return; }
        for (char ch : mp[digs.charAt(i) - 48].toCharArray()) {  // 该数字对应字母
            path.append(ch);
            backtrack(i + 1, path);
            path.deleteCharAt(path.length() - 1);
        }
    }
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) return ans;
        digs = digits;
        backtrack(0, new StringBuilder());
        return ans;
    }
}

def bt(i, path):
    if i == 总位数:
        res.append(path 的快照); return
    for 选项 in 第 i 位的候选:
        path.append(选项)
        bt(i + 1, path)          # 关键：i+1 下探
        path.pop()               # 撤销

void backtrack(int i, Path& path) {
    if (i == 总位数) { res.push_back(path 的快照); return; }
    for (选项 ch : 第 i 位的候选) {
        path.push_back(ch);
        backtrack(i + 1, path);   // 关键: i+1 下探
        path.pop_back();          // 撤销
    }
}

void backtrack(int i, StringBuilder path) {
    if (i == 总位数) { res.add(path.toString()); return; }
    for (char ch : 第 i 位的候选) {
        path.append(ch);
        backtrack(i + 1, path);   // 关键: i+1 下探
        path.deleteCharAt(path.length()-1);  // 撤销
    }
}

复杂度

面试官可能追问