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

电话号码字母组合在问什么

给一个只含 2 到 9 的数字串，每个数字像老式电话键盘那样对应几个字母（2 对 abc、3 对 def，7 和 9 各对 4 个），要求列出这串数字能表示的所有字母组合。以 "23" 为例，第一个字母从 abc 里挑、第二个从 def 里挑，共 3×3 等于 9 种。本质上这是在求「每位各选一个字母」的所有搭配方式，也就是若干组候选字母的笛卡尔积，而且要全部列出来，不是数个数。

为什么不用嵌套循环而用回溯

两位数字写两层循环、三位写三层，思路没错，但输入的位数是变量，循环层数没法写死，代码无法对任意长度通用。这是所有「层数不定的枚举」共同的困境。

出路是把「一层循环」换成「一层递归」：定义 backtrack(i) 表示正在为第 i 位数字挑字母，函数体里一个 for 循环枚举这一位的候选，选中一个就递归到 backtrack(i + 1) 处理下一位。递归深度自动等于数字位数，等于用一个函数写出了任意层的嵌套循环——这正是回溯算法处理这类枚举题的通用骨架。

path 和递归参数 i 的含义要先钉死

参数 i 表示前 i 位数字都已选好字母、现在轮到第 i 位；path 里存的正是这前 i 个字母。两者构成一条不变量：任何时刻 path 的长度恰好等于 i。于是终止条件水到渠成——当 i 等于 digits 的长度，说明每一位都选过了，把 path 连接成字符串收进结果即可。

每层的候选集合由 digits 的第 i 个字符查表得到，比如查到 "def" 就依次尝试 d、e、f。同一层的三个选择彼此平行，各自往下展开一棵子树，所有叶子加起来正好是全部组合，不重也不漏。

为什么递归回来必须 pop 掉刚选的字母

path 是整棵递归树共享的同一个缓冲区，不是每层复制一份。递归从 backtrack(i + 1) 返回时，意味着「以刚才那个字母打头的所有后续组合」已经收集完毕，必须把它从 path 末尾弹出，恢复到选它之前的状态，才能在同一层干净地换下一个字母。不弹的话，上一个选择会残留在 path 里污染后面的分支，拼出的字符串位数和内容全错。先 append、递归、再 pop，这三步的对称性就是回溯正确性的全部保证。

复杂度与两个必踩的边界

时间 O(4ⁿ·n)：每位最多 4 个候选字母（数字 7 和 9），组合总数最多 4ⁿ 个，每个组合拼成字符串还要 O(n)。空间 O(n)：递归深度与 path 长度都等于位数，结果本身不计。

两个边界最容易翻车：一是 digits 为空必须直接返回空数组，而不是含一个空串的数组——没有输入就没有任何组合；二是映射表要从 2 开始建，0 和 1 不对应字母，且 7 对 pqrs、9 对 wxyz 各是 4 个字母，错位一格全盘皆输。

Java

class Solution {
    private static final String[] MAP = {
        "", "", "abc", "def", "ghi",
        "jkl", "mno", "pqrs", "tuv", "wxyz"
    };
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits == null || digits.isEmpty()) return res;
        backtrack(digits, 0, new StringBuilder(), res);
        return res;
    }
    private void backtrack(String digits, int i,
                           StringBuilder path, List<String> res) {
        if (i == digits.length()) {        // 选满了
            res.add(path.toString());      // 收集一个组合
            return;
        }
        String letters = MAP[digits.charAt(i) - '0'];
        for (int k = 0; k < letters.length(); k++) {
            path.append(letters.charAt(k));     // 选一个字母
            backtrack(digits, i + 1, path, res);
            path.deleteCharAt(path.length() - 1); // 回溯
        }
    }
}

Python

class Solution:
    def letterCombinations(self, digits: str):
        if not digits:
            return []
        MAP = {"2": "abc", "3": "def", "4": "ghi",
               "5": "jkl", "6": "mno", "7": "pqrs",
               "8": "tuv", "9": "wxyz"}
        res, path = [], []
        def backtrack(i):
            if i == len(digits):        # 选满了
                res.append("".join(path))   # 收集组合
                return
            for ch in MAP[digits[i]]:   # 这一位的候选字母
                path.append(ch)         # 选一个
                backtrack(i + 1)
                path.pop()              # 回溯
        backtrack(0)
        return res

C++

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if (digits.empty()) return res;
        const string MAP[10] = {
            "", "", "abc", "def", "ghi",
            "jkl", "mno", "pqrs", "tuv", "wxyz"};
        string path;
        function<void(int)> backtrack = [&](int i) {
            if (i == (int)digits.size()) {   // 选满了
                res.push_back(path);         // 收集组合
                return;
            }
            for (char ch : MAP[digits[i] - '0']) {
                path.push_back(ch);          // 选一个字母
                backtrack(i + 1);
                path.pop_back();             // 回溯
            }
        };
        backtrack(0);
        return res;