17. 电话号码的字母组合

LeetCode 原题链接

题目描述

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

数字与字母的对应关系如下：

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"]
输入：digits = ""
输出：[]
输入：digits = "2"
输出：["a", "b", "c"]

1. 题型判断

输入中的每个数字都代表一组候选字母。要生成一个完整答案，需要依次从每个数字对应的字母集合中选择一个字母。

例如 digits = "23"：

第 0 层，从 abc 中选择一个字母
第 1 层，从 def 中选择一个字母
选择两个字母后，得到一个完整组合

每一层负责一个确定位置，枚举该位置的所有候选，再继续处理下一位。这天然形成一棵决策树，因此适合使用回溯。

本题不需要 visited 数组，也不需要 start 下标：

  • 每层处理的数字位置由递归参数 index 决定。
  • 不同层的字母可以相同，不存在“某个元素只能使用一次”的限制。
  • 每条从根到叶子的路径天然对应唯一组合，不会产生重复答案。

2. 状态定义

回溯过程中维护三个核心状态：

  • index：当前要处理 digits 中的第几个数字。
  • path：前 index 个数字已经选择的字母。
  • ans：保存所有已经生成的完整组合。

每次进入递归函数时保持以下不变量：

path.length === index

也就是说，path 中恰好保存了 digits[0..index - 1] 对应的选择，下一个字符必须从 digits[index] 对应的字母集合中产生。

3. 回溯过程

递归函数 backtrack(index) 的处理步骤如下：

  1. 如果 index === digits.length，说明每个数字都已经选择了一个字母，将当前路径加入答案。
  2. 否则找到 digits[index] 对应的候选字母。
  3. 依次枚举每个候选字母：
    • 做选择：将字母加入 path。
    • 递归：处理下一个数字，即 backtrack(index + 1)。
    • 撤销选择：删除刚加入的字母，恢复当前层的状态。

核心结构是：

for (const letter of letters) {
  path.push(letter);
  backtrack(index + 1);
  path.pop();
}

push 与 pop 必须成对出现。这样从一个分支返回后，才能在相同的父路径上尝试下一个字母。

4. 示例推演

对于 digits = "23"，决策树为：

                     ""
             /        |        \
            a         b         c
          / | \     / | \     / | \
         d  e  f   d  e  f   d  e  f

叶子节点从左到右依次得到：

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

以第一个分支为例：

操作indexpath说明
初始调用0[]准备处理数字 2
选择 a1[a]继续处理数字 3
选择 d2[a, d]到达叶子，记录 ad
撤销 d1[a]尝试同层的下一个字母
选择 e2[a, e]记录 ae
撤销 e1[a]继续尝试 f

处理完 a 的所有分支后撤销 a，再以同样方式处理 b 和 c。

5. 代码实现

解法一：回溯

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  if (digits.length === 0) {
    return [];
  }

  const phone = {
    2: "abc",
    3: "def",
    4: "ghi",
    5: "jkl",
    6: "mno",
    7: "pqrs",
    8: "tuv",
    9: "wxyz",
  };

  const ans = [];
  const path = [];

  const backtrack = (index) => {
    if (index === digits.length) {
      ans.push(path.join(""));
      return;
    }

    const letters = phone[digits[index]];

    for (const letter of letters) {
      path.push(letter);
      backtrack(index + 1);
      path.pop();
    }
  };

  backtrack(0);
  return ans;
};

为什么叶子节点要复制路径

path 是整个搜索过程复用的可变数组。如果直接把 path 放入答案，后续的 push 和 pop 会继续修改同一个数组对象。

本题需要字符串结果，所以在叶子节点执行：

ans.push(path.join(""));

这一步会根据当前路径创建一个新的字符串，后续回溯不会影响已经保存的答案。

6. 正确性说明

可以从“不遗漏、不重复、只产生合法答案”三个方面说明：

  • 不遗漏：在第 index 层，算法会遍历当前数字对应的每个字母，并对每种选择递归处理剩余数字，因此所有可能的选择序列都会被访问。
  • 不重复：每个答案由各数字位置上的选择唯一确定。两条不同的根到叶路径至少有一个位置选择不同，所以不会生成相同路径。
  • 合法性：只有当 index === digits.length 时才记录答案，此时路径恰好为每个输入数字选择了一个对应字母，长度也与 digits 相同。

因此，算法生成的结果恰好是题目要求的全部字母组合。

7. 复杂度分析

设输入长度为 n，其中有 a 个数字对应 3 个字母，有 b 个数字对应 4 个字母，且 a + b = n。

组合总数为：

3^a × 4^b

每个答案的长度为 n，生成字符串需要 O(n) 时间，因此：

  • 时间复杂度：O(n × 3^a × 4^b)，最坏为 O(n × 4^n)。
  • 空间复杂度：
    • 不计返回结果时为 O(n)，包括递归调用栈和路径数组。
    • 计入返回结果时为 O(n × 3^a × 4^b)。

结果本身就有 3^a × 4^b 个，因此无法把总体运行时间优化为多项式级别。

8. 解法二：迭代展开

也可以从只包含空字符串的列表开始，每处理一个数字，就把已有组合与该数字的每个候选字母拼接，生成新一轮组合。

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  if (digits.length === 0) {
    return [];
  }

  const phone = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
  let combinations = [""];

  for (const digit of digits) {
    const next = [];
    const letters = phone[Number(digit) - 2];

    for (const combination of combinations) {
      for (const letter of letters) {
        next.push(combination + letter);
      }
    }

    combinations = next;
  }

  return combinations;
};

迭代法与回溯法本质相同：它们都逐层展开同一棵决策树。回溯使用递归栈深度优先遍历，迭代法显式保存当前层的所有部分结果。

9. 边界条件与易错点

边界条件：

  • digits 为空时应返回 []，而不是 [""]。
  • 单个数字会直接返回该按键上的所有字母。
  • 数字 7 和 9 各对应 4 个字母，其余有效数字对应 3 个字母。
  • 根据题目约束，输入只含 2～9，无需处理 0 和 1。

易错点：

  • 递归终止条件是 index === digits.length，不是 index === digits.length - 1。
  • 做出选择后必须在递归返回时撤销，否则不同分支的字符会混在一起。
  • 保存答案时要将可变路径转换为独立字符串。
  • 不要错误地给本题添加去重逻辑；每个位置代表不同数字位，即使候选字母恰好相同也属于独立选择。
  • 使用数组保存映射时，下标应为 Number(digit) - 2。

10. 面试追问

本题需要剪枝吗？

不需要。每个中间路径都能继续扩展为合法答案，没有无效分支可以提前排除。题目的指数级规模来自必须输出所有组合，而不是搜索了多余状态。

为什么不需要 visited？

visited 通常用于同一批候选中某个元素只能使用一次的排列问题。本题每层的候选由当前位置的数字单独决定，进入下一层后自然处理下一个数字，不会重复使用某个输入位置。

回溯和迭代哪个更好？

两者的渐进时间复杂度相同。回溯更直接地表达“每个位置选择一个字母”，辅助空间较小；迭代法没有递归调用，但需要保存整层的中间组合。面试中回溯通常更容易讲清状态与搜索树。

如果需要按字典序输出怎么办？

当前映射中的字母本身按字典序排列，输入位置也从左到右处理，因此深度优先搜索自然产生字典序结果。如果映射顺序不确定，应先对每个数字的候选字母排序。

11. 可迁移总结

本题体现的是固定层数的选择模型：

第 0 个位置选一个候选
  -> 第 1 个位置选一个候选
    -> ...
      -> 所有位置选择完成，记录答案

遇到“从多个候选集合中各选一个元素，生成全部组合”的问题时，可以使用同样的回溯框架：

  1. 用递归层数表示当前处理的集合。
  2. 遍历该集合中的所有候选。
  3. 做选择后递归下一层。
  4. 返回时撤销选择。
  5. 处理完所有集合时记录路径。

笛卡尔积、分段选择以及按位置构造字符串等问题都可以沿用这一思路。