电话号码的字母组合 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

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

示例 1

输入：digits = "23"

输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2

输入：digits = "2"

输出：["a","b","c"]

💭 模拟答题者思考

1. 我先想暴力：对每一位数字，枚举它映射里的每个字母，笛卡尔积式地拼出所有串——思路对，但要写出「逐位扩展」的结构。

2. 重复在哪里？每多处理一位，就是在已有前缀后面接一个新字母；子问题变成「从第 idx 位开始，把剩余位数补全」。

3. 优化成回溯：固定 path 表示当前前缀，idx 表示处理到第几位；对 digits[idx] 的每个候选字母递归下一层。

4. 终止条件：idx == len(digits) 时 path 已是完整组合，加入 ans；否则枚举当前位字母，选、递归、撤销。

5. 特判 digits == "" 应返回空列表；最多 4 位、每位最多 4 个字母，回溯深度 ≤ 4，非常安全。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`path`	str / list	定义：当前已选字母拼成的部分组合（前缀）维护：每处理一位数字，从映射中选一个字母追加到末尾更新：递归前 `path += ch`；回溯时撤销（`pop` 或切片还原）
`idx`	int	定义：当前要处理 `digits` 中的第几位（下标）维护：每选定一个字母并递归返回后，进入下一位更新：初始为 0；每轮枚举完当前位所有字母后 `idx++`（由递归参数传递）
`mapping`	dict / array	定义：数字键到对应字母串的固定映射表维护：程序启动时一次性建好，全程只读更新：不更新；用 `digits[idx]` 查表得到候选字母集合
`ans`	list<str>	定义：所有长度等于 `len(digits)` 的合法组合维护：当 `idx == len(digits)` 时，将当前 `path` 的副本加入更新：每到达叶子层追加一次；不在中途追加半成品

⌨️ 落码步骤

1. 建立 2-9 到字母串的映射表 mapping

2. 若 digits 为空，直接返回 []

3. 定义 DFS backtrack(idx, path)：若 idx == len(digits)，将 path 加入 ans 并返回

4. 取 letters = mapping[digits[idx]]，对每个字母 ch：追加到 path，递归 backtrack(idx+1, path)，再撤销追加

5. 从 backtrack(0, "") 启动，返回 ans

💻 代码实现

class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []

        mapping = {
            "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
        }
        ans: list[str] = []

        def backtrack(idx: int, path: list[str]) -> None:
            if idx == len(digits):
                ans.append("".join(path))
                return
            for ch in mapping[digits[idx]]:
                path.append(ch)
                backtrack(idx + 1, path)
                path.pop()

        backtrack(0, [])
        return ans

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};

        static const vector<string> mapping = {
            "", "", "abc", "def", "ghi", "jkl",
            "mno", "pqrs", "tuv", "wxyz"
        };
        vector<string> ans;
        string path;

        function<void(int)> dfs = [&](int idx) {
            if (idx == (int)digits.size()) {
                ans.push_back(path);
                return;
            }
            int d = digits[idx] - '0';
            for (char ch : mapping[d]) {
                path.push_back(ch);
                dfs(idx + 1);
                path.pop_back();
            }
        };

        dfs(0);
        return ans;
    }
};
// 时间 O(4^n · n)，空间 O(n)（递归栈，不计输出）

📈 复杂度分析

时间复杂度 O(4^n · n)

空间复杂度 O(n)（递归栈，不计输出）

⚠️ 常见坑

❗ 忘记空串特判：digits = "" 时必须返回 []，不能返回 [""]。

❗ 回溯不撤销：选完字母递归后必须 pop，否则 path 会越积越长，污染兄弟分支。

❗ 把数字当数组下标直接用：'2' 的 ASCII 是 50，应使用 digits[idx] - '0' 或映射字典查表。

🔍 必测边界 Case

Case 1：空输入

digits = "" → []

Case 2：单个数字

digits = "2" → ["a","b","c"]

Case 3：四位全满（每位 4 字母）

digits = "79" → 16 种组合（7 有 4 个字母，9 有 4 个字母）