电话号码的字母组合

题目描述

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

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

示例

示例 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'] 的数字

我的解题过程

❌ 最初的错误思路

一开始我尝试用循环的方式解决，但这个思路是错误的：

function letterCombinations(digits: string): string[] {
  const map: Record<string, string> = {
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz",
  };
  let res = [];

  for (let i = 0; i < digits.length; i++) {
    const cur = digits[i];
    res.push(map[cur]);
  }

  let result = [];
  let curIndex = 0;
  let stringIndex = 0;
  while (curIndex < res.length - 1) {
    result.push(res[curIndex][stringIndex] + res[curIndex + 1][stringIndex]);
    stringIndex++;

    if (stringIndex === res[curIndex].length - 1) {
      curIndex++;
      stringIndex = 0;
    }
  }

  return result;
}

为什么这个方法不行？

1. 问题1：组合逻辑错误 - 我只是简单地按相同索引组合字符（第i个和第i个组合），这根本不是笛卡尔积
   • 例如 “23”：我想组合 res[0][0] + res[1][0] → “ad”，然后 res[0][1] + res[1][1] → “be”
   • 但实际需要的是：a要和d、e、f都组合，b也要和d、e、f都组合，c也要和d、e、f都组合
2. 问题2：只处理了两个数字 - 代码只循环到 res.length - 1，只能处理相邻的两个数字
   • 如果输入是 “234”，我的代码无法生成所有3个数字的组合
3. 问题3：stringIndex++ 的错误逻辑 - 我假设两个字符串长度相同，但实际上不同数字对应的字母数量不同
   • “7” 对应 “pqrs” (4个字母)
   • “2” 对应 “abc” (3个字母)
   • 当处理完 “abc” 的3个字母后，“pqrs” 还有第4个字母没处理

正确的解法：回溯算法（树形结构）

看了题解后才明白，这道题的本质是一个多叉树遍历问题。

树形结构图解（以 “23” 为例）

                    root
                 /    |    \
                a     b     c       (数字2的选择)
              / | \  / | \ / | \
             d  e f  d e f d e f    (数字3的选择)

结果: [ad, ae, af, bd, be, bf, cd, ce, cf]

更详细的树形结构和路径追踪：

                        ""
                    /   |   \
                  a     b     c      ← 第1层：选择数字'2'的字母
               /  |  \
             d    e    f             ← 第2层：选择数字'3'的字母

路径追踪（深度优先遍历）：
1. "" → a → d  ✓ 到达叶子节点，收集结果 "ad"，回溯到 a
2. "" → a → e  ✓ 收集 "ae"，回溯到 a
3. "" → a → f  ✓ 收集 "af"，回溯到 root
4. "" → b → d  ✓ 收集 "bd"，回溯到 b
5. "" → b → e  ✓ 收集 "be"，回溯到 b
6. "" → b → f  ✓ 收集 "bf"，回溯到 root
7. "" → c → d  ✓ 收集 "cd"，回溯到 c
8. "" → c → e  ✓ 收集 "ce"，回溯到 c
9. "" → c → f  ✓ 收集 "cf"，结束

回溯算法实现

function letterCombinations(digits: string): string[] {
  if (!digits) return [];

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

  const result: string[] = [];

  function backtrack(index: number, current: string) {
    // 递归终止条件：已经处理完所有数字
    if (index === digits.length) {
      result.push(current);
      return;
    }

    // 获取当前数字对应的字母
    const letters = map[digits[index]];

    // 遍历当前数字对应的每个字母
    for (let i = 0; i < letters.length; i++) {
      // 选择当前字母，进入下一层递归
      backtrack(index + 1, current + letters[i]);
      // 回溯：不需要显式撤销，因为字符串是不可变的
    }
  }

  backtrack(0, "");
  return result;
}

解题思路

核心概念：回溯 = 深度优先遍历 + 路径记录

这道题是典型的组合问题，需要找出所有可能的字母组合。可以看作是一棵多叉树：

• 树的每一层代表一个数字
• 每个节点的分支数量等于该数字对应的字母数量
• 从根节点到叶子节点的路径就是一个完整的组合

算法步骤：

1. 边界处理：如果输入为空字符串，直接返回空数组
2. 定义映射表：创建数字到字母的映射关系
3. 回溯函数 backtrack(index, current)：
   • index：当前处理的数字位置
   • current：当前已经组合的字符串
4. 递归终止条件：当 index === digits.length 时，说明所有数字都处理完了，将当前组合加入结果
5. 递归过程：
   • 获取当前数字对应的所有字母
   • 遍历每个字母，将其加入当前组合
   • 递归处理下一个数字
   • 由于字符串不可变，不需要显式回溯

回溯模板：

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        result.add(路径);
        return;
    }

    for (选择 in 选择列表) {
        做选择;
        backtrack(路径, 选择列表);
        撤销选择;
    }
}