力扣-17. 电话号码的字母组合（Letter Combinations of a Phone Number）

最后编辑于2025-06-28

17. 电话号码的字母组合（Letter Combinations of a Phone Number）

Medium

给定一个仅包含数字 2-9 的字符串，返回所有该数字可能表示的字母组合（电话按钮映射）。可以按任意顺序返回答案。
alt text

示例 1：

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

示例 2：

输入： digits = ""
输出： []

示例 3：

输入： digits = "2"
输出： ["a","b","c"]

约束：

  • 0 <= digits.length <= 4
  • digits[i] 为字符 ‘2’ 至 ‘9’

思路与常见解法

本题是典型的组合枚举问题，常用解法为：

  • 回溯（递归）：按位枚举当前数字对应的每个字符，递归构造字符串直到长度等于输入长度，然后加入结果集。
  • 迭代（BFS 风格）：将结果视为一层一层扩展的状态，从初始的空串开始，依次把当前数字对应的字符追加到已有的每个字符串后面，得到新一层结果。

无论递归还是迭代，首先都要建立数字到字符串的映射表（例如 ‘2’ -> “abc”）。

方法一：回溯（递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> res;
        vector<string> dict{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        dfs(digits, dict, 0, "", res);
        return res;
    }
    void dfs(const string& digits, const vector<string>& dict, int pos, string cur, vector<string>& res) {
        if (pos == digits.size()) { res.push_back(cur); return; }
        string str = dict[digits[pos] - '0'];
        for (char ch : str) dfs(digits, dict, pos + 1, cur + ch, res);
    }
};
  • 时间复杂度： O(3^n * 4^m)（n 为映射到 3 个字母的数字个数，m 为映射到 4 个字母的数字个数）
  • 空间复杂度： O(n)（递归栈 + 结果空间）

方法二：迭代（逐位扩展）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> res{"");
        vector<string> dict{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        for (char d : digits) {
            vector<string> t;
            string str = dict[d - '0'];
            for (char ch : str) {
                for (const string& s : res) t.push_back(s + ch);
            }
            res.swap(t);
        }
        return res;
    }
};
  • 说明： 迭代写法逻辑直观且无需递归，适合不喜欢递归的场景。

作者想说的话：
电话号码字母组合是练习回溯和树形状态遍历的好题：回溯递归对应 DFS，迭代扩展对应 BFS，两种方法都很直观，按需选择即可。