Letter Combinations of a Phone Number 是 LeetCode Hot 100 里面一道非常典型的回溯题。
这道题本身不难，代码量也不大，但它非常适合用来理解 回溯算法的基本写法
你给出的这份 Java 代码，就是这道题最经典的写法之一： 通过一个映射表，把数字映射成对应字母，然后使用递归一层层构造所有可能的字符串组合。
本文就结合这段代码，系统地讲一下这道题的解法思路。
题目介绍
给定一个仅包含数字 2-9 的字符串 digits，返回它所能表示的所有字母组合。
数字和字母之间的映射关系与手机按键相同：
-
2对应"abc" -
3对应"def" -
4对应"ghi" -
5对应"jkl" -
6对应"mno" -
7对应"pqrs" -
8对应"tuv" -
9对应"wxyz"
例如输入：
"23"
因为：
-
2可以表示a、b、c -
3可以表示d、e、f
所以最终所有组合就是：
["ad","ae","af","bd","be","bf","cd","ce","cf"]
题目要求我们把这些组合全部返回。
示例
示例 1
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
因为第一个位置有 3 种选择，第二个位置也有 3 种选择，所以总共有：
3 × 3 = 9
种组合。
示例 2
输入：digits = "" 输出：[]
如果输入是空字符串，就没有任何可组合的结果，因此直接返回空列表。
示例 3
输入：digits = "2" 输出：["a","b","c"]
因为数字 2 对应 "abc"，所以答案就是这三个单字符字符串。
这道题为什么适合用回溯？
我们先从问题本质来看。
假设输入是：
digits = "23"
那么第一位可以从 "abc" 中选一个，第二位可以从 "def" 中选一个。
也就是说，我们需要：
-
先决定第 1 个位置填什么
-
再决定第 2 个位置填什么
-
当所有位置都填完之后，就得到一个完整答案
这其实就是一个非常标准的“逐层决策”问题。
再比如输入：
"279"
那么流程就变成：
-
第 1 层：从
2 -> abc中选一个 -
第 2 层：从
7 -> pqrs中选一个 -
第 3 层：从
9 -> wxyz中选一个
每一层都要做选择，而所有路径走完之后，就能得到全部结果。
这正是回溯算法最擅长处理的场景。
核心思路
我们可以把整个过程想象成一棵树。
以 digits = "23" 为例：
-
第一层可以选择
a、b、c -
对于每一个选择，第二层又可以继续选择
d、e、f
整棵树展开之后，大概就是这样：
a -> d -> e -> f b -> d -> e -> f c -> d -> e -> f
每一条从根到叶子的路径，都是一个合法答案。
所以我们只需要写一个递归函数，不断往路径里添加字符；当路径长度等于 digits.length() 时，就说明一个组合已经构造完成，把它加入结果集中即可。
Java 代码
下面就是你给出的代码，我保留原始写法，并加上注释方便理解：
class Solution {
String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> result = new ArrayList<>();
public List<String> letterCombinations(String digits) {
// 特殊情况：输入为空，直接返回空结果
if (digits == null || digits.isEmpty()) return result;
// 从下标 0 开始回溯，当前路径为空
backtrack(digits, 0, new StringBuilder());
return result;
}
private void backtrack(String digits, int index, StringBuilder sb) {
// 如果已经处理到最后一个数字之后，说明当前组合构造完成
if (index == digits.length()) {
result.add(sb.toString());
return;
}
// 获取当前数字
char digit = digits.charAt(index);
// 根据映射表找到它对应的字母
String letters = mapping[digit - '0'];
// 枚举当前数字对应的每一个字母
for (char letter : letters.toCharArray()) {
sb.append(letter); // 做选择
backtrack(digits, index + 1, sb); // 进入下一层
sb.deleteCharAt(sb.length() - 1); // 撤销选择
}
}
}
代码拆解
这段代码不长，但它把回溯的核心结构体现得非常完整。 如果你正在学回溯，这份代码其实很有代表性。
1. 映射表的作用
String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
这里用一个字符串数组来保存数字和字母的对应关系。
比如：
-
mapping[2] = "abc" -
mapping[3] = "def" -
mapping[7] = "pqrs"
当我们拿到某个数字字符，比如 '2' 时，就可以通过：
mapping[digit - '0']
快速找到它对应的字母集合。
这里的 digit - '0'，本质上是把字符数字转换成真正的整数下标。
例如：
-
'2' - '0' = 2 -
'7' - '0' = 7
这是 Java 里一个很常见的小技巧。
2. 为什么空字符串要直接返回？
if (digits == null || digits.isEmpty()) return result;
因为题目要求返回所有可能的字母组合。
如果输入本身就是空字符串，那么根本没有任何数字可以参与组合，自然也就没有结果。
所以这里直接返回空列表即可。
这一步虽然简单，但一定不能漏掉，否则有些测试用例会出问题。
3. backtrack 函数的含义是什么？
private void backtrack(String digits, int index, StringBuilder sb)
这个函数有三个参数：
-
digits：输入的数字字符串 -
index：当前处理到了第几个数字 -
sb：当前已经构造出的路径
换句话说，它表示的是：
当前已经确定了前 index 个位置的字符，现在要继续处理第 index 个数字。
这个定义非常关键。
只要你把它理解清楚，整个回溯流程就会变得很自然。
4. 什么时候递归结束？
if (index == digits.length()) {
result.add(sb.toString());
return;
}
当 index == digits.length() 时，说明所有数字都已经处理完了。
也就是说，当前这条路径已经构造成了一个完整答案。
这时候就应该把它加入结果集，然后返回上一层。
这就是回溯中的“终止条件”。
5. 当前层到底在做什么？
char digit = digits.charAt(index);
String letters = mapping[digit - '0'];
这里先拿到当前数字，再找到它对应的字母集合。
例如：
-
如果当前数字是
'2' -
那么
letters = "abc"
接下来这一层要做的事情，就是从 "abc" 中依次选择一个字母，放到当前路径里。
这就是所谓的“枚举当前层的所有选择”。
6. 回溯三部曲
for (char letter : letters.toCharArray()) {
sb.append(letter);
backtrack(digits, index + 1, sb);
sb.deleteCharAt(sb.length() - 1);
}
这一段就是最典型的回溯模板。
可以拆成三步来看：
第一步：做选择
sb.append(letter);
把当前字母加入路径。
第二步：递归进入下一层
backtrack(digits, index + 1, sb);
去处理下一个数字。
第三步：撤销选择
sb.deleteCharAt(sb.length() - 1);
把刚才加入的字符删掉，让路径恢复到进入这一层之前的状态。
这样下一轮循环时，才能尝试别的字母。
这一步就是“回溯”这个名字的来源。
手动模拟一遍
我们用最经典的例子来走一下流程：
digits = "23"
一开始调用：
backtrack("23", 0, "")
第 1 层
当前数字是：
'2'
对应字母：
"abc"
所以第一层有三个选择：
-
选
a -
选
b -
选
c
先选 a
路径变成：
"a"
然后递归进入下一层。
第 2 层
当前数字是：
'3'
对应字母：
"def"
于是继续有三个选择：
-
选
d，得到"ad" -
选
e，得到"ae" -
选
f，得到"af"
当走到 "ad" 时，index == digits.length()，说明一个完整组合已经形成，加入结果集。
之后回退，再尝试 "ae"、"af"。
再选 b
同理，会得到：
-
"bd" -
"be" -
"bf"
再选 c
会得到：
-
"cd" -
"ce" -
"cf"
最终结果就是：
["ad","ae","af","bd","be","bf","cd","ce","cf"]
为什么要用 StringBuilder？
很多人看到这里会问，为什么不用普通的字符串拼接，而要用：
StringBuilder sb
原因主要有两个：
第一，效率更高
如果每次递归都用字符串拼接，比如：
path + letter
那么会频繁创建新的字符串对象，效率会差一些。
而 StringBuilder 可以在原有基础上直接追加和删除字符，更适合这种“不断修改路径”的场景。
第二，更符合回溯模型
回溯的本质就是：
-
添加一个选择
-
递归
-
再撤销这个选择
StringBuilder 的 append 和 deleteCharAt 正好非常适合这种操作。
复杂度分析
假设输入字符串长度为 n。
每个数字最多对应 4 个字母（比如 7 和 9）。
所以总的组合数量大约是：
3^n 或 4^n
更准确地说，时间复杂度可以写成：
O(4^n * n)
因为总共有这么多种组合，而每个组合生成时大约要处理 n 个字符。
空间复杂度
空间复杂度主要来自递归调用栈和路径构造：
O(n)
如果把最终结果集也算进去，那么结果所占空间会更大，但通常分析时单独讨论返回结果。
这道题真正想考什么？
这道题表面上是在考手机按键映射，实际上真正考的是：
你会不会写最基础的回溯模板。
因为它的结构特别标准：
-
先判断终止条件
-
找到当前层可选的元素
-
枚举每一种选择
-
做选择、递归、撤销选择
这几步几乎就是之后所有回溯题的共同骨架。
比如后面你再学到：
-
全排列
-
子集
-
组合总和
-
N 皇后
你会发现它们的代码框架都和这道题非常像。
所以这道题虽然不算难，但非常值得认真理解。
总结
这道题的核心思路其实很简单：
-
每个数字对应一组字母
-
我们从左到右，依次为每个位置选择一个字母
-
当所有位置都选完时，就得到一个完整答案
因此最适合的做法就是：
回溯 + 递归构造路径
这道题的关键点主要有三个：
-
用映射表保存数字到字母的对应关系
-
用
index表示当前处理到第几个数字 -
用
StringBuilder记录路径，并在递归后撤销选择
如果你刚开始学习回溯，这道题非常适合作为入门练习。 因为它没有复杂的剪枝，也没有特别绕的边界条件，重点非常纯粹，就是让你熟悉“路径、选择、递归、回退”这一整套流程。
把这道题真正写熟之后，再去做全排列、组合、子集这些题，你会明显感觉顺手很多。
