Sign in Subscribe
算法

电话号码的字母组合

loser

• 5 min read
Share

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

数字到字母的映射与电话按键相同，数字 1 不对应任何字母。

示例 1：

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

示例 2：

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

提示：

  • 1 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字

回溯：

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

        vector<string> letters = {
            "", "", "abc", "def", "ghi",
            "jkl", "mno", "pqrs", "tuv", "wxyz"
        };

        vector<string> ans;
        string path;
        backtrack(digits, 0, letters, path, ans);
        return ans;
    }

private:
    void backtrack(const string& digits, int index, const vector<string>& letters, string& path, vector<string>& ans) {
        if (index == digits.size())
        {
            ans.push_back(path);
            return;
        }

        int digit = digits[index] - '0';
        for (char ch : letters[digit])
        {
            path.push_back(ch);
            backtrack(digits, index + 1, letters, path, ans);
            path.pop_back();
        }
    }
};

核心思想

这题本质上是在做多层选择。

对于 digits 中的每一位数字，都有若干个可选字母：

2 -> a, b, c
3 -> d, e, f
7 -> p, q, r, s
9 -> w, x, y, z

每个最终答案都必须从每一位数字对应的字母中选出一个，并且保持数字原来的顺序。

因此可以使用回溯来枚举所有可能：

  1. 当前处理到第 index 位数字。
  2. 枚举这个数字对应的所有字母。
  3. 选择一个字母加入当前路径 path。
  4. 递归处理下一位数字。
  5. 递归结束后撤销选择，继续尝试其他字母。

回溯树

以 digits = "23" 为例：

第 1 层：从 2 对应的 a, b, c 中选一个
第 2 层：从 3 对应的 d, e, f 中选一个

形成的组合为：

ad, ae, af
bd, be, bf
cd, ce, cf

每一条从根节点到叶子节点的路径，就是一个完整的字母组合。

递归参数

void backtrack(const string& digits, int index, const vector<string>& letters, string& path, vector<string>& ans)

各参数含义如下：

  • digits：原始数字字符串。
  • index：当前正在处理第几个数字。
  • letters：数字到字母的映射表。
  • path：当前已经选择出的字母组合。
  • ans：保存所有完整组合。

其中 path 是一个临时路径，长度始终等于已经处理过的数字个数。

递归终止条件

当 index == digits.size() 时，说明所有数字都已经处理完，当前 path 就是一个完整组合：

if (index == digits.size())
{
    ans.push_back(path);
    return;
}

此时需要把 path 加入答案，然后返回上一层继续搜索其他选择。

选择与撤销

对于当前数字：

int digit = digits[index] - '0';

可以通过映射表得到它对应的字母集合：

letters[digit]

然后依次选择每个字母：

path.push_back(ch);
backtrack(digits, index + 1, letters, path, ans);
path.pop_back();

其中：

  • push_back 表示做选择。
  • 递归调用表示继续处理下一位数字。
  • pop_back 表示撤销选择，让当前层可以尝试下一个字母。

这就是标准的「选择 - 递归 - 撤销」回溯流程。

正确性证明

结论 1：算法生成的每个字符串都是合法组合

递归每一层只处理 digits 中的一个数字，并且只从该数字对应的字母集合中选择一个字母加入 path。

当递归到 index == digits.size() 时，path 的长度等于 digits 的长度，并且每一位字母都来自对应数字的映射。

因此算法生成的每个字符串都是合法的电话号码字母组合。

结论 2：所有合法组合都会被生成

任意一个合法组合，都可以看成对每一位数字选择一个对应字母。

算法在第 index 层会遍历 digits[index] 对应的所有字母，因此不会漏掉该位置的任何可能选择。

递归会依次处理所有位置，所以任意合法组合对应的选择路径都会被搜索到。

因此所有合法组合都会被生成。

结论 3：不会生成重复组合

题目中每个数字对应的字母集合内部没有重复字母。

算法每一层按照当前位置的数字枚举字母，不会重复枚举同一个选择。

不同递归路径至少在某一层选择的字母不同，因此生成的字符串也不同。

所以算法不会生成重复组合。

综上，算法能够正确返回所有电话号码可能表示的字母组合。

示例分析

以 digits = "23" 为例：

初始：path = ""

选择 a -> 继续处理 3 -> 得到 ad, ae, af
选择 b -> 继续处理 3 -> 得到 bd, be, bf
选择 c -> 继续处理 3 -> 得到 cd, ce, cf

最终答案为：

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

复杂度分析

设 digits 的长度为 n。

  • 时间复杂度：O(n * 4^n)。每一位数字最多对应 4 个字母，最多生成 4^n 个组合；每个组合加入答案时需要复制长度为 n 的字符串。
  • 空间复杂度：O(n)。递归调用栈和临时路径 path 的长度最多为 n。如果计入返回结果，空间复杂度为 O(n * 4^n)。

边界情况

  • digits 只有一位：直接返回该数字对应的所有单个字母。
  • digits 中包含 7 或 9：这两个数字对应 4 个字母，循环会自然处理。
  • digits 为空：虽然题目限制长度至少为 1，代码仍做了保护，返回空数组。