电话号码的字母组合：回溯算法与DFS递归的经典入门题解

周末刷力扣的时候，碰到57. 电话号码的字母组合这道题。说实话，这道题在力扣热题100里算是一道非常经典的“回溯”入门题，但别看它难度标着Medium，其实核心思想并不复杂，很多刚接触DFS回溯的朋友容易被“映射 + 组合”这两个点绕晕。我这篇就把这道题从题目本质到代码实现，再到常见的坑和优化思路，完整地拆开揉碎讲一遍。

1. 题目本质与核心思路拆解

这道题的题干大家应该都见过：给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。数字到字母的映射和电话九宫格一样，比如2对应abc，3对应def，以此类推。

很多新手看到这个题的第一反应是：这有什么难的，几个for循环嵌套不就完了？但问题在于，输入的数字长度是未知的。如果长度是3，写三层循环；长度是5，写五层循环——显然不可能这么干。这就引出了回溯算法最核心的价值：用递归的方式处理不确定层数的循环嵌套。

举个例子，输入"23"，你需要在脑海中构建这样一棵树：

• 从数字2开始，它有a、b、c三个分支
• 每个分支下接数字3的d、e、f三个分支
• 从根到叶子节点的每一条路径，就是一个完整的字母组合

DFS回溯在这里做的事情，就是沿着一条路径走到黑（深度优先），走不动了（处理完最后一个数字）就记录结果，然后回退一步，尝试另一个分支。这就像你在一个迷宫里探索，走到死胡同就原路返回，换一个岔路口再走。

这里有个非常关键的设计点：递归函数的参数设计。我见过很多人在这一关卡住。通常我们需要两个参数：

• index：当前处理到第几位数字了
• path：当前已经拼接好的字符串路径

为什么需要index？因为你要知道递归什么时候该停。为什么需要path？因为你要记录当前这条路径上已经选了哪些字母。这两个参数是回溯算法最基础的“状态”概念。

注意：这道题里我们不需要像全排列那样维护一个visited数组，因为数字键盘上每个数字对应的字母是互斥的，同一层不可能重复选同一个位置的字母，天然不存在重复访问的问题。

2. 映射表的构建与细节处理

题目给了数字到字母的映射关系，但没直接给你数据结构。这其实是个很基础的编码问题，但不同的人处理方式天差地别。

2.1 数组映射是最稳妥的方案

有些朋友喜欢用Map<Integer, String>，然后一个个put，这样写起来啰嗦，而且容易漏。我推荐直接用字符串数组，用索引做下标匹配，非常干净：

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

这里有个细节要注意：0和1在电话键盘上不对应任何字母，所以映射为空字符串。很多人在定义数组的时候会漏掉这两个位置，导致下标错位。我的习惯是把数组长度设为10，下标直接对应数字，这样避免做digit - '0' - 2之类的偏移计算，减少心智负担。

2.2 字符转数字的两种方式

拿到字符串后，我们要取每一位数字，转成int去查表。常见的写法有两种：

// 方式一：字符减字符 int num = digits.charAt(index) - '0'; // 方式二：String.valueOf + Integer.parseInt int num = Integer.parseInt(String.valueOf(digits.charAt(index)));

我强烈推荐方式一，因为它高效且简洁。'0'的ASCII码是48，'2'的ASCII码是50，相减直接得到整数2，一步到位。方式二做了太多没必要的类型转换，在刷题时属于多余操作。

2.3 空输入的特殊处理

这里有一个极易踩坑的点：输入空字符串时，应该返回什么？

很多人的第一反应是返回空列表[]，但题目要求明确说了：如果输入为空，返回空列表。但你仔细想想，如果传入""，我们递归函数里第一行就判断index == digits.length()，此时会直接执行path.append()然后加入结果集，最终得到一个包含空字符串的列表[""]——这就错了。

所以必须在主函数里提前判断：

if (digits == null || digits.length() == 0) { return new ArrayList<>(); }

这个判断看似简单，但真的很重要。我刷题的时候见过不少代码，测试用例一跑，空的输入直接报错或返回错误结果，都是栽在这个细节上。

3. 回溯算法完整实现与逐行解读

接下来是重头戏：完整的代码实现。我用Java来写，因为力扣上Java是最主流的语言之一，但思路是通用的，换成Python、C++完全一样。

import java.util.ArrayList; import java.util.List; class Solution { // 数字到字母的映射表 private static final String[] MAPPING = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; public List<String> letterCombinations(String digits) { List<String> result = new ArrayList<>(); // 空输入特殊处理 if (digits == null || digits.length() == 0) { return result; } // 开始回溯 backtrack(digits, 0, new StringBuilder(), result); return result; } private void backtrack(String digits, int index, StringBuilder path, List<String> result) { // 递归终止条件：处理完所有数字 if (index == digits.length()) { result.add(path.toString()); return; } // 当前数字对应的字母串 String letters = MAPPING[digits.charAt(index) - '0']; // 遍历当前数字的每一个字母 for (int i = 0; i < letters.length(); i++) { // 做选择：把当前字母加入路径 path.append(letters.charAt(i)); // 递归处理下一位数字 backtrack(digits, index + 1, path, result); // 撤销选择：回溯的关键一步 path.deleteCharAt(path.length() - 1); } } }

3.1 递归终止条件的设计逻辑

终止条件是index == digits.length()，意思是所有数字都处理完毕。此时path里存的已经是一个完整的组合，直接加入结果集。

这里有个面试官常问的考点：为什么不用index == digits.length() - 1作为终止条件？因为这样最后一个数字的字母还没有被遍历到，逻辑会在最后一层循环里多走一轮，反而麻烦。用index == digits.length()是最自然、最不容易出错的写法，代码的语义和物理含义完全对应。

3.2 为什么用StringBuilder而不是String拼接

很多初学者喜欢这么写：

backtrack(digits, index + 1, path + letters.charAt(i), result);

这样写其实也能跑通，因为String的+拼接本质上是在创建新字符串，回溯时不需要手动撤销。但问题在于，Java里字符串是不可变的，每次拼接都会创建新的对象，在递归层数较深或分支较多时，会有额外的内存开销和GC压力。

用StringBuilder的好处是：同一个对象可以被反复修改。做选择时append，撤销时deleteCharAt，全程只维护一个路径对象，内存效率高得多。

不过用StringBuilder也有个坑：如果你直接把path对象加入结果集，后续对path的修改会影响已经加入的结果。所以必须用path.toString()生成一个新的字符串快照，再放入result。我在实战中就见过同学栽在这上面，结果所有结果集里的字符串全都变成一模一样的了。

3.3 回溯的三步曲

整个backtrack函数内部就是回溯算法最经典的三步：

1. 做选择：path.append(letters.charAt(i))
2. 递归进入下一层：backtrack(digits, index + 1, path, result)
3. 撤销选择：path.deleteCharAt(path.length() - 1)

第三步“撤销”是回溯和普通递归的本质区别。没有这一步，path会一直累积下去，最终得到的结果是"ad"、"ade"、"adef"这种越来越长的残留路径，完全不是我们要的组合。

我用生活中的场景来类比：你在橱柜里挑搭配，先拿了一件上衣，再看裤子，搭配完一套记下来，然后必须把上衣放回去，才能拿另一件上衣继续搭配。撤销选择就是“把上衣放回去”的动作，没有它，你的手里永远是上一套衣服，没法尝试新的组合。

4. 时间复杂度与空间复杂度分析

这道题的复杂度分析也是面试中常见的考点。虽然代码简单，但复杂性分析却能区分出你是不是真正理解了递归的本质。

4.1 时间复杂度

假设输入的数字个数为n，每个数字最多对应4个字母（7和9对应4个，其余对应3个）。那么组合的总数最坏情况是4^n。

递归树中，每个叶子节点对应一个完整的组合，每个组合的拼接操作是O(n)。所以：

• 最坏时间复杂度 = 组合总数 × 每次生成组合的代价 =O(4^n * n)

这里的n即输入数字字符串的长度。对于力扣的测试数据而言（长度通常不超过4），这个复杂度完全在可接受范围内，但如果你真去处理长度10以上的输入，结果集会爆炸式增长，内存都装不下。

4.2 空间复杂度

空间复杂度主要由两部分组成：

• 递归调用栈的深度：O(n)
• 结果集占用的空间：O(4^n * n)

所以总的空间复杂度是O(4^n * n)。严格来说，递归栈本身只占O(n)，但结果集才是大头。不过通常面试回答时，说空间复杂度O(4^n * n)是比较严谨的。

提示：有些资料会把空间复杂度写成O(n)，这也没有错，因为它们只算了递归栈的额外空间，忽略了结果集本身。讨论复杂度时，先明确“是否包含输出结果”这个前提，避免面试时各说各话。

5. 常见问题与排查技巧

这道题虽然不难，但实际写代码时踩坑的点还挺多的。我总结几个我见过的、以及我自己踩过的坑，供大家参考。

5.1 问题一：返回结果顺序不对

有些朋友写完代码一跑，发现结果集顺序和预期不一样，比如"bd"排在"ad"前面。这里要说清楚：力扣对这道题的输出顺序其实有要求，必须按照字典序（其实就是DFS的遍历顺序）排列。

如果你用的遍历顺序是“先遍历后一个数字的字母，再遍历前一个数字的字母”，那顺序自然就反了。解决办法很简单：递归时始终从左到右处理数字，循环内也按字母表顺序遍历，DFS天然的遍历顺序就是答案要求的顺序。

5.2 问题二：StringBuilder被复用导致结果全是最后一个

这是我见过最经典的错误：

result.add(path); // 错误！应该用 path.toString()

如果你直接把path加入结果集，那么之后path的任何修改都会反映在result里的“所有”元素上。最终你得到的结果集，会是多个指向同一个StringBuilder的引用，里面全是最后一次回溯完的状态。

排查方法也很简单：在result.add(path.toString())前后打印path的内容，你会发现加入时是正确的，但最终结果却全变成了最后一个。这就是典型的“引用传递”问题。

5.3 问题三：递归深度和栈溢出

理论上，输入长度为n时递归深度就是n。力扣的测试数据长度有限，不会栈溢出。但如果你把这道题的思路扩展到无限长度的输入，就要考虑递归深度的问题了。

实际工作中，如果需要处理超长数组，可以改用显式的栈来模拟回溯过程，或者用迭代法（BFS）逐层扩展。力扣这道题用递归完全没问题，但理解迭代法的思路能帮你应对更复杂的变种题。

5.4 问题四：回溯撤销操作遗漏

很多新手写完“递归”忘记“撤销”，导致路径无限累积。这里我分享一个自查技巧：在递归函数里，做选择和撤销选择一定要对称。每一层append，最终必然对应一次deleteCharAt。你可以数一数，每个分支的结尾，path.length()应该回到进入该分支前的长度。

还有一个小技巧：如果忘记写撤销，得到的path长度永远不会等于digits.length()，所以在if (index == digits.length())里加一个打印，看看path的结果，立刻就能发现问题。

6. 回溯算法的模式提炼与举一反三

这道题解决之后，千万别急着划走。我强烈建议你把它当作“回溯算法”的模板题，认真总结一下通用套路。回溯算法的代码结构几乎都是同一个模板：

void backtrack(参数) { if (满足终止条件) { 记录结果; return; } for (选择 : 所有可选选择) { 做选择; backtrack(更新后的参数); 撤销选择; } }

掌握了这个模板，你就解锁了一大批力扣的经典题目：

• 46. 全排列：需要加visited数组避免重复选择
• 78. 子集：每个元素选或不选
• 17. 电话号码的字母组合（也就是本题）：从不同数字对应的字母集合中各选一个
• 39. 组合总和：可以重复选择同一元素
• 131. 分割回文串：需要额外判断回文

这些题的区别，主要在于“选择空间”的定义方式不同。全排列的选择空间是“还没被选过的所有元素”，本题的选择空间是“当前数字对应的几个字母”。想明白了这一点，你就不会被题目的表面形式迷惑，而能直击回溯的本质。

我在刷题时习惯把回溯题的代码结构先在纸上画一遍递归树，明确每一层的“选择列表”是什么、终止条件是什么、需要撤销什么，然后再写代码，基本能做到一次通过。

7. 从“AC”到“真懂”：进阶优化思路

如果上面的内容你已经完全掌握了，我再给你多聊几句进阶的内容。这道题虽然官方解法就是DFS回溯，但有些细节还能继续优化，以及有一些变体思路值得了解。

7.1 用队列实现BFS版本

回溯（DFS）的思想是深度优先，一路走到头再回头。但很多人可能没想到，这道题也可以用BFS（广度优先）来做，思路是逐层扩展：

public List<String> letterCombinations(String digits) { LinkedList<String> queue = new LinkedList<>(); if (digits.isEmpty()) return queue; String[] mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; queue.offer(""); for (int i = 0; i < digits.length(); i++) { String letters = mapping[digits.charAt(i) - '0']; int size = queue.size(); for (int j = 0; j < size; j++) { String cur = queue.poll(); for (char c : letters.toCharArray()) { queue.offer(cur + c); } } } return queue; }

BFS版本的好处是代码更短，不需要显式地管理递归状态。每次从队列里取出当前层已有的字符串，尝试追加下一个数字的每个字母，再放回队列。等所有数字都处理完，队列里存的就是全部组合。这个思路在打印层序遍历、求最短路径等场景里也很有用。

不过从“刷题面试”的角度，DFS回溯还是更主流、更通用，因为回溯能解决更多更灵活的排列组合问题，而BFS这个写法比较依赖逐层扩展的规则。

7.2 剪枝思路的启发

这道题本身几乎没有剪枝空间，因为每个字母都是合法的组合路径。但从“回溯优化”的思想出发，字符串拼接时会有大量中间状态产生。如果输入特别长，可以提前用StringBuilder的容量初始化来减少扩容开销，或者像之前说的，用char[]数组替代StringBuilder，在指定位置赋值再撤销，进一步降低创建对象的成本。

不过说实话，这些优化在力扣的数据范围内意义不大，我更建议把精力花在对“回溯模板”的理解和变体题的迁移上。

7.3 为什么这道题是“进大厂必刷”的入门必备

你可能也发现了，力扣热题100里回溯相关的题不算少，但这道题被放在很靠前的位置，原因就在于它足够“纯粹”。它不涉及复杂的剪枝条件，不用担心重复元素，不需要维护额外的访问标记数组。它把回溯最核心的骨架——做选择、递归、撤销选择——完整地展现出来了，没有任何多余的修饰。

当我刚接触回溯时，其实也是从这道题入门的。因为我一开始完全看不懂那些递归套递归的写法，后来静下心来，把这道题的递归树手动画了一遍，突然就通了。所以说，这道题是理解DFS回溯的“杠杆点”，花一两个小时彻底搞懂它，后面再刷十道回溯题都会轻松很多。

我在实际给朋友讲题时，最常推荐的方法就是：拿张纸，把"23"的递归树画出来，然后在代码里每个函数入口和出口各打一行日志，亲眼看着path怎么增长、怎么回退。这个过程走一遍之后，回溯对你来说就不再是玄学了，而是有章可循的思维工具。