Hot 100 --- 电话号码的字母组合

本文概览：本文以LeetCode题目"电话号码的字母组合"为例，讲解回溯法在多选一场景下的应用，和子集方法二的模板对比

---

一、题目

二、题目分析

题目要求：给定一个数字字符串（2-9），每个数字对应一组字母（手机九宫格键盘），从每个数字对应的字母中各取一个，组合成新字符串，返回所有可能的组合

数字到字母的映射表：

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

比如 digits = "23"：2 对应 "abc"，3 对应 "def"，从 "abc" 取一个，从 "def" 取一个，组合起来

a + d → "ad"    a + e → "ae"    a + f → "af"
b + d → "bd"    b + e → "be"    b + f → "bf"
c + d → "cd"    c + e → "ce"    c + f → "cf"

共 3 × 3 = 9 种组合

这题和子集方法一（选/不选决策树）的思路很像——都是对每个位置做选择，递归到最深处收集结果。区别是：子集每个元素可以选也可以不选，这题每个数字必须选一个字母，相当于把决策树里所有"不选"的分支全砍掉，只保留"选"的分支一路走到底

---

思路概览

class Solution {
   private final String[] map = {
            "",      // 0
            "",      // 1
            "abc",   // 2
            "def",   // 3
            "ghi",   // 4
            "jkl",   // 5
            "mno",   // 6
            "pqrs",  // 7
            "tuv",   // 8
            "wxyz"   // 9
    };

    private final StringBuilder sb = new StringBuilder();

    private final List<String> result = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) {
            return new ArrayList<>();
        }
        backtrack(digits, 0);
        return result;
    }

    private void backtrack(String digits, int index) {
        // 递归出口
        if (index == digits.length()) {
            result.add(sb.toString());
            return;
        }
        // 递归过程
        String letter = map[digits.charAt(index) - '0'];
        for (int i = 0; i < letter.length(); i++) {
            // 从当前数字对应的字符串中选取一个字符
            sb.append(letter.charAt(i));
            // 递归
            backtrack(digits, index + 1);
            // 回溯
            sb.deleteCharAt(sb.length() - 1);
        }

    }
}

思路简要说明

1. 映射表：用数组存数字到字母的映射，索引就是数字本身，map[2] = "abc"
2. index 标记处理到第几个数字：每次取出 digits.charAt(index) 对应的字母串，for 循环选一个字母往下递归
3. 只在叶子节点收集：index == digits.length 时，所有数字都选完了，把 StringBuilder 转成 String 存入结果

---

三、思路详解

第一步：映射表的设计

数字 2-9 对应字母，怎么存？最直接的方式是用数组，索引就是数字：

private final String[] map = {
    "",      // 0（没有对应字母）
    "",      // 1（没有对应字母）
    "abc",   // 2
    "def",   // 3
    "ghi",   // 4
    "jkl",   // 5
    "mno",   // 6
    "pqrs",  // 7
    "tuv",   // 8
    "wxyz"   // 9
};

取数字 3 对应的字母串：map[3] → "def"，O(1) 查询

0 和 1 没有对应字母，放空字符串占位，这样数字直接当索引用，不需要额外转换

第二步：和子集方法一（选/不选决策树）的对比

子集方法一每个元素有"选"和"不选"两个分支，递归 n 层到叶子节点收集结果。这题每个数字必须选一个字母，相当于把"不选"分支全砍掉：

子集方法一的决策树（nums = [1, 2]）：

根
├─ 选1
│   ├─ 选2  → {1,2}
│   └─ 不选2 → {1}
└─ 不选1
    ├─ 选2  → {2}
    └─ 不选2 → {}

本题的决策树（digits = "23"）——没有"不选"分支，每层必须选一个：

根（处理数字2）
├─ 选a
│   ├─ 选d → "ad"
│   ├─ 选e → "ae"
│   └─ 选f → "af"
├─ 选b
│   ├─ 选d → "bd"
│   ├─ 选e → "be"
│   └─ 选f → "bf"
└─ 选c
    ├─ 选d → "cd"
    ├─ 选e → "ce"
    └─ 选f → "cf"

每个节点都往下选，不存在"不选"的分支，所以只在叶子节点（所有数字都选完）收集结果

	子集（方法一）	电话号码的字母组合
分支方式	每个元素两个分支：选 / 不选	每个数字必须选一个字母，没有不选分支
收集时机	只在叶子节点收集	只在叶子节点收集
递归参数	index（当前处理第几个）	index（当前处理第几个数字）
回溯操作	add / removeLast	append / deleteCharAt
树的形态	满二叉树（2ⁿ 个叶子）	多叉树（每层分叉数 = 字母数）

核心区别：子集有"不选"分支所以是满二叉树，本题没有"不选"分支，每层分叉数取决于当前数字对应几个字母

第三步：index 参数的作用

index 表示当前处理到第几个数字，每层 index+1。以 digits = "23" 为例：

backtrack(index=0, sb="")
├── append 'a' → backtrack(index=1, sb="a")     ← 处理数字 '2'，对应 "abc"
│   ├── append 'd' → backtrack(index=2, sb="ad") ← 处理数字 '3'，对应 "def"
│   │   └── index == 2 == digits.length()，收集 "ad"
│   ├── append 'e' → backtrack(index=2, sb="ae")
│   │   └── 收集 "ae"
│   └── append 'f' → backtrack(index=2, sb="af")
│       └── 收集 "af"
├── append 'b' → backtrack(index=1, sb="b")
│   ├── ...（同上，收集 "bd", "be", "bf"）
└── append 'c' → backtrack(index=1, sb="c")
    └── ...（同上，收集 "cd", "ce", "cf"）

digits.charAt(index) - '0' 把字符转成数字，比如 '2' - '0' = 2，然后 map[2] 拿到 "abc"

第四步：回溯操作

回溯的两个动作：

• append = 选：sb.append(letter.charAt(i))，选了第 i 个字母往下递归
• deleteCharAt = 撤销换下一个：sb.deleteCharAt(sb.length() - 1)，删掉最后一个字母，for 循环 i++ 选下一个

以数字 '2' 对应 "abc" 为例：

选 'a' → 递归 → 回溯（删掉 'a'）
选 'b' → 递归 → 回溯（删掉 'b'）
选 'c' → 递归 → 回溯（删掉 'c'）

每次选完一个字母往深处走，回来后撤销，for 循环选下一个，这就是回溯的核心

第五步：完整执行过程

以 digits = "23" 为例，2 对应 "abc"，3 对应 "def"：

backtrack(index=0, sb="")
├── append 'a' → backtrack(index=1, sb="a")
│   ├── append 'd' → backtrack(index=2, sb="ad")
│   │   └── 收集 "ad"                    ← ①
│   ├── remove 'd'
│   ├── append 'e' → backtrack(index=2, sb="ae")
│   │   └── 收集 "ae"                    ← ②
│   ├── remove 'e'
│   ├── append 'f' → backtrack(index=2, sb="af")
│   │   └── 收集 "af"                    ← ③
│   └── remove 'f'
├── remove 'a'
├── append 'b' → backtrack(index=1, sb="b")
│   ├── append 'd' → backtrack(index=2, sb="bd")
│   │   └── 收集 "bd"                    ← ④
│   ├── remove 'd'
│   ├── append 'e' → backtrack(index=2, sb="be")
│   │   └── 收集 "be"                    ← ⑤
│   ├── remove 'e'
│   ├── append 'f' → backtrack(index=2, sb="bf")
│   │   └── 收集 "bf"                    ← ⑥
│   └── remove 'f'
├── remove 'b'
├── append 'c' → backtrack(index=1, sb="c")
│   ├── append 'd' → backtrack(index=2, sb="cd")
│   │   └── 收集 "cd"                    ← ⑦
│   ├── remove 'd'
│   ├── append 'e' → backtrack(index=2, sb="ce")
│   │   └── 收集 "ce"                    ← ⑧
│   ├── remove 'e'
│   ├── append 'f' → backtrack(index=2, sb="cf")
│   │   └── 收集 "cf"                    ← ⑨
│   └── remove 'f'
└── remove 'c'

结果：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]，共 9 个 = 3 × 3

第六步：StringBuilder vs String 拼接

代码中用 StringBuilder 而不是 String 拼接：

// ✗ String 拼接，每次创建新对象
String path = "";
path += 'a';  // 新对象 "a"
path += 'd';  // 新对象 "ad"

// ✓ StringBuilder，在原对象上操作
StringBuilder sb = new StringBuilder();
sb.append('a');  // 同一个对象
sb.append('d');  // 同一个对象

回溯需要频繁增删字符，StringBuilder 的 append 和 deleteCharAt 都是 O(1)，而 String 拼接每次创建新对象效率低

复杂度分析

• 时间复杂度：O(3ⁿ × 4ᵐ)，其中 n 是对应 3 个字母的数字个数，m 是对应 4 个字母的数字个数（7 和 9 对应 4 个字母）。最坏情况 O(4ⁿ)
• 空间复杂度：O(n)，递归深度最大为 n（数字个数），StringBuilder 最多存 n 个字符