电话号码字母组合：回溯算法入门与DFS/BFS实现

最近在带一位准备校招的同学刷力扣热题100刷到第17题“电话号码的字母组合”时他问了一个特别典型的问题这题明明用好几层循环也能写为什么要用回溯我想很多第一次刷到这道题的人都有这个疑惑所以干脆把这道题的拆解、递归思路、DFS与BFS两种实现以及我实际刷题和面试里踩过的细节坑一起整理成一篇完整的记录。这道题本身不复杂输入是一个只含2到9的数字字符串输出这些数字能映射出的全部字母组合。比如输入232对应abc3对应def输出就是ad、ae、af、bd、be、bf、cd、ce、cf这九种。它是理解回溯算法最顺滑的入门题之一也是后面做全排列、组合总和、子集这些题的地基。不管你是刚准备刷算法的新手还是想把回溯模板彻底搞懂的老手这篇都值得看完。1. 题目到底在问什么先搞懂这道经典题1.1 题面拆解输入输出举例先花一分钟把题面彻底读透。函数签名通常是def letterCombinations(digits: str) - List[str]:输入是一个字符串比如23567或者空串。输出是一个字符串列表包含所有可能的字母组合。电话拨号盘上2到9每个数字对应一组字母2 - abc3 - def4 - ghi5 - jkl6 - mno7 - pqrs8 - tuv9 - wxyz注意7和9对应的是四个字母其他都是三个。这个细节后面算复杂度和构造测试用例的时候会用到先记在这里。举例验证一下输入 2输出 [a, b, c]输入 23输出 [ad, ae, af, bd, be, bf, cd, ce, cf]输入 234输出 3乘以3乘以3等于27种组合组合的数量是每个按键字母数量的乘积。输入有几个数字结果字符串就有多长。这里要特别明确一个基本规则组合的顺序按输入数字的先后次序来第一个数字选一个字母第二个数字选一个字母这样依次选完。题目只要求组合不要求排列所以ad和da不会同时出现因为第一个位置只能放到2映射的字母。1.2 为什么Hot 100把它放在靠前位置核心考点这道题在力扣热题100里属于“回溯”这个分类下的入门位置。它其实同时考察三个点是否理解穷举的本质所有组合本质上是一棵多叉树的叶子节点树的每一层对应输入中的一个数字每个节点的分支数等于当前数字映射的字母个数。是否掌握递归和函数调用栈的关系递归到第几层对应处理到第几个数字。是否理解回溯中的状态恢复这个位置选a还是选b选完之后怎么回到上一层继续选下一个。这三个点不偏不倚正好是后续所有回溯题的骨架。你把这题吃透后面做“组合总和”“全排列”“N皇后”这些题脑子里自然会浮现同一张递归树。1.3 一种常见的错误先入为主很多人第一次看到这题第一反应是暴力循环既然最多4位数字那就写4层for循环呗。这种思路对付长度上限为4的测试用例确实能过但有个致命问题题目如果改成输出所有长度为20的组合循环嵌套层数就直接爆炸了。而且从面试角度来说面试官想看的不是你会不会写for循环而是你对递归结构的理解。所以正确姿势是把每个数字看作递归树的一层每一层用循环处理当前数字能选的字母处理完一层就递归进入下一层。这个思维转变一旦完成代码量反而比多层循环更少也更通用。2. 为什么不能暴力循环递归拆解每一层的选择2.1 嵌套循环的致命局限数字位数不定先说清楚为什么嵌套循环不是正解。假设输入固定是23你写两层循环很舒服。但输入变成234呢三层循环。变成2345呢四层循环。输入长度是不固定的循环嵌套层数也要动态变这在代码层面根本没法直接写死。更深层的问题是暴力循环把问题的结构搞错了。这个问题本质上可以递归定义处理第i个数字时先选一个字母然后处理剩下的i1到最后的数字。这种“处理完当前位置、接着处理剩余部分”的结构天然就是递归的形态硬要用循环去模拟就相当于用手动栈去实现递归调用既绕又容易出错。2.2 建立数字到字母的映射表第一步先建映射。这一步非常基础但有一个细节值得说用数组而不用字典查询更快也更简洁。mapping [, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz]数组下标0和1留空因为数字0和1在电话键盘上没有对应字母。当输入是23时取出mapping[2]得到abc取出mapping[3]得到def。用字符串切片或者for循环逐个取出字母都可以。如果要用字典长这样phone { 2: abc, 3: def, ... }两种写法都能过但用数组的好处有两个第一按下标访问是O(1)且没有哈希开销第二代码更干净面试官一眼能看懂。笔试场景下性能差异微乎其微纯属个人偏好但我会在分享中默认推荐数组写法。2.3 递归树把一个组合问题变成树形遍历把问题画成树是最关键的一步。输入23的递归树结构如下根节点后面跟着三个分支a、b、c从a出发再跟着三个分支ad、ae、af从b出发再跟着三个分支bd、be、bf从c出发再跟着三个分支cd、ce、cf整棵树一共三层根节点是第0层处理第一个数字深度为1的节点各对应一个字母叶子节点就是最终结果。DFS的过程就是沿着树的路径一直往下走走到叶子就记录一个结果然后回头换另一条路继续走。这个树的深度等于输入长度分支数量由当前数字映射的字母数决定。这棵树的规模就是结果数量比如23是9个叶子节点。理解这棵树后代码就是照着树的遍历逻辑来写def dfs(index, path): if index len(digits): res.append(.join(path)) return for ch in mapping[int(digits[index])]: path.append(ch) dfs(index 1, path) path.pop()3. 核心动作入栈、递归、出栈三件套3.1 为什么必须撤销恢复现场才能回到上一层回溯算法里最核心、也最容易被忽略的一个动作就是撤销也就是那行path.pop()。很多人第一次写会漏掉它或者不理解为什么要它。用一个比喻来说明你在走迷宫每到一个岔路口选一条路走进去走到底发现是死胡同必须退回到上一个岔路口重新选择另一条路。这个“退回到岔路口”的动作对应到代码里就是把path中当前加进去的字母弹出来。如果不弹出来path会越积越长从一条路径莫名其妙变成所有路径内容混在一起。每一步递归调用结束之后path中应当只保留“从根到当前节点”的路径。加上一个字母进入下一层回到本层后再移除这个字母保证循环里的下一次迭代从同样的起点出发。这就是恢复现场。3.2 用列表加pop还是用字符串拼接实现上有一个常见的二选一path用list加pop还是用字符串相加。# 方式一list append/pop path.append(ch) dfs(index 1, path) path.pop() # 方式二字符串直接拼接无显式撤销 dfs(index 1, path ch)方式二其实没有“撤销”动作因为path ch生成了一个新的字符串原字符串没有变所以会自然而然回到上一层。它的代码更短不少新手喜欢用。但方式二有两个问题。第一每次拼接都产生一个新字符串在组合数量大的时候会有额外的内存与时间开销。虽然这道题最多4位数字结果最多几百个完全不构成压力但养成习惯对后续其他题有影响。第二它隐藏了“回溯”的本质让人以为不需要恢复现场。等遇到需要修改共享状态才能高效解题的题目时会一脸懵。所以我的建议是初学时用方式一把append、递归、pop三件套刻进肌肉记忆。这个三件套在几乎所有回溯题里都一样练熟之后看任何回溯题都和看老朋友一样。3.3 收集结果的时机index到底等于几终止条件的判断是另一个容易出错的点。dfs(index, path)中index表示当前要处理第几个数字。当index len(digits)时说明所有数字都已经处理完了当前path就是一个完整结果。也许有人会问为什么不是index len(digits) - 1时收集因为第index层的循环体里我们会先选字母再进入dfs(index 1)。也就是说最后一个数字的字母是在dfs(len(digits) - 1)的循环中选择的选完之后path已经包含最后一个字母然后调用dfs(len(digits))。此时path长度正好等于输入长度但path已经被选择完整了。所以必须在index len(digits)时收集而不是在递归之前判断。这个边界虽然小但面试时很容易说错或者写错建议在草稿纸上演算一遍2这个输入把dfs的调用过程写出来。4. 换一条路径用队列迭代实现BFS版本4.1 队列层序扩展的思路DFS是从上到下一条路走到黑BFS则是按层扩展。思路是先把一个空串放进队列然后每处理一个数字就从队列中取出当前所有前缀把当前数字对应的字母逐个拼接成新串再放回队列。这样处理完所有数字后队列中就是全部结果。用23来演示整个过程初始队列[]处理2取出拼接a、b、c队列变成[a, b, c]处理3取出a拼接d、e、f得到ad, ae, af再取出b拼接得到bd, be, bf再取出c拼接得到cd, ce, cf最终队列里的元素就是全部组合。这种写法不需要显式写递归函数思路更接近“每一层的迭代扩展”代码往往更短。4.2 代码演示与逐行分析def letterCombinations(digits: str): if not digits: return [] mapping [, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz] queue [] for digit in digits: letters mapping[int(digit)] queue [prefix ch for prefix in queue for ch in letters] return queue这里有个关键点queue [prefix ch for prefix in queue for ch in letters]这行是在创建新列表而不是在原queue上原地修改。如果你写成for prefix in queue: for ch in letters: queue.append(prefix ch)就会在遍历queue的同时修改queue导致重复处理无限膨胀。这个坑我见过很多人踩BFS写法看起来简单但生成新列表这个动作恰恰避开了迭代时修改容器的错误。4.3 DFS与BFS两种写法怎么选两种写法本质解决同一个问题选哪种主要看场景和个人习惯。对比维度DFS递归BFS队列代码复杂度需要写递归函数和撤销动作逻辑平铺直叙代码短空间复杂度递归栈深度O(n)队列最多O(3^n)数量级结果顺序深度优先顺序例如ad, ae, af...广度优先顺序例如ad, bd, cd, ae...对回溯机制的理解帮助大为后续难题打基础帮助较小偏向用迭代技巧适合场景解空间树复杂、需要剪枝的题只需按层扩散、状态简单的问题这道题两种都能过但我个人倾向先用DFS因为它的思维方式更通用。后面遇到更难的回溯题BFS几乎没有用武之地但DFS配合剪枝几乎是万能模板。5. 复杂度、边界和三个容易犯的错5.1 时间复杂度务必要自己会算算法题面试里复杂度分析是考完代码后的必问题。这道题的复杂度不是一刀切的O(2^n)或者O(n^2)得根据数字对应的字母数量来拆分。设输入中对应3个字母的数字2、3、4、5、6、8有m个对应4个字母的数字7、9有n个那么组合总数是3的m次方乘以4的n次方。对每个组合最后拼接字符串还需要O(L)时间这里L等于输入长度digits.length()所以总时间复杂度是O(3^m * 4^n * L)。空间复杂度方面递归深度是O(L)每个递归栈帧需要保存当前path而辅助空间主要是path列表所以不算结果集的话额外空间是O(L)。如果把结果集本身也算进去那自然是O(3^m * 4^n * L)。这个复杂度一定要会推导因为面试官很可能会追问如果输入是9999结果有多少个那就是4的4次方等于256个。如果输入是2222结果有多少个3的4次方等于81个。都能手算心里要有数。5.2 边界用例清单从空串到单键再到四字母键实际写代码时测试用例不要只测题目给的示例。我刷题时习惯准备这么一组digits 返回空列表[]而不是包含一个空字符串的[]。这是最容易判断错的边界因为空串也是一个输入但没有任何数字可映射所以没有任何组合。digits 2返回[a, b, c]长度等于3验证单数字场景。digits 7返回[p, q, r, s]长度等于4验证四字母按键不会漏。digits 79两个四字母键结果是16个组合。digits 23题目示例9个组合用于和其它实现对比。尤其是空串这个边界很多解法一上来就mapping[int(digits[0])]取第一个字符直接越界或者报错。正确做法是在函数开头就判断if not digits: return []5.3 三个我踩过且反复见到的写法错误先看第一个坑把映射表下标搞反。有人会写成mapping[letter]想通过字母反查数字但这题只需要从数字到字母的正向映射方向搞反之后代码会变得非常别扭。建议就在函数里放数组按下标访问不搞花活。第二个坑递归参数传错。dfs(index 1, path)写成了dfs(index 1, path ch)然后还保留了path.pop()。这会产生双重叠加一边手动往path加字母一边又靠字符串拼接传新路径最后结果里会出现重复字符或者错误组合。要记住方式一和方式二是两套方案不要混着用。第三个坑收集结果的时机写在循环里。有人会把res.append(.join(path))放在for循环内部结果同一个路径被重复记录多次。正确位置是在index len(digits)的终止条件里收集一次。这三个坑说大不大但在面试紧张时极容易暴露。每次写完代码口头跑一遍23的流程基本都能自查出来。5.4 从模拟面试角度看这题怎么答如果是在面试现场遇到这题我的建议是按这个顺序推进先把题面转述清楚确认输入输出“输入是字符串包含2到9输出是所有可能的字母组合顺序无关。”提一句边界空串返回空列表。画递归树和面试官沟通思路每个数字对应一层每一层循环当前数字映射的字母选一个进入下一层选完要撤销走到最后收集结果。写代码边写边说终止条件、分支逻辑、撤销操作。最后手动验证23顺便把复杂度算给面试官看。整个流程控制在一道普通回溯题该有的节奏里不慌不忙。6. 同模板的兄弟题目从字母组合延伸到后续进阶题6.1 一套回溯模板打天下把这题做完你会发现回溯题其实是一个模子刻出来的。随手总结一套通用模板def backtrack(参数): if 满足结束条件: 记录结果 return for 选择 in 当前层可选项: 做选择 backtrack(更新后的参数) 撤销选择第17题是这套模板最简单直接的应用。它唯一的特殊点在于没有剪枝条件——所有分支都是合法的不需要提前判断“这个方向能不能走”。再往后做“组合总和”模板还是在只是多了一个排序加剪枝做“全排列”模板多了一个used数组来避免重复选同一个元素做“N皇后”模板多了对对角线和列冲突的判断。理解了这一题的树形结构后面就是把树的每层变成不同的约束条件而已。6.2 变体一只要组合数量不输出具体组合有一种常见变体题目改成给定数字串求一共有多少种字母组合不要求列出组合本身。比如“已知2映射三个字母3映射三个字母输入23时有多少组合”答案就是3乘3等于9。这种变体本质上是数学乘法原理根本不用回溯直接遍历数字串做乘法即可。但如果题目变成带约束的数量统计比如“某些数字因为某种原因不能选某个字母”那就要回到回溯模板在循环体里加一个判断条件跳过违规项。这种题的难点从“怎么写回溯”转移到了“剪枝条件怎么设计”。6.3 变体二允许排列或要求顺序全不同再一种变体是不要求“每个数字的位置固定选一个字母”而是把字母看作一个集合要求输出所有可能的排列或组合。这就把输入数字映射出来的字母全部摊平再套用全排列模板。此时used数组、去重逻辑、startIndex这些概念就都会出现了。从第17题出发去理解这些变体一个核心收获是回溯题的树结构才是根本具体参数怎么传、剪枝怎么加都是围绕着那棵树在做文章。6.4 我的实操体会先画递归树再写代码最后分享一点我的实际经验。带同学刷题这几年我发现很多人写回溯题卡住原因不是不会写循环而是没在脑子里建立递归树。我自己的习惯是拿到题先不急着写代码先在草稿纸上画三个节点标出第一层可以选哪些、走到第二层会有什么分支、什么时候到达叶子。树一画出来终止条件、循环范围、撤销动作全都一目了然。画完树之后写代码还有三个小技巧可以分享参数越少越好。dfs只传当前层数和路径别把一堆无关状态塞进去否则传参心态先崩。终止条件永远是递归函数的第一行不要写在后面。写完代码后做一次小规模手算验证用23这种长度短的输入一行一行模拟递归过程比干瞪着代码效率高得多。我自己也犯过那种“代码看着对跑起来结果不对”的毛病后来发现基本都出在撤销动作或者边界判断上。所以现在每写一道回溯题我都会刻意把这三个点检查一遍终止条件是否第一时间处理、循环是否能覆盖所有分支、撤销是否保证每次递归返回后状态一致。这题虽然只是热题100里的第17题但它承载的思维量一点都不小。建议看完这篇后自己动手写一遍DFS版本再用BFS版本对比着跑一遍同样的测试用例。两套都能一遍过的时候你对这道题、对回溯的理解就都到位了。