最近帮一个正在准备算法面试的朋友梳理经典的DFS入门题翻来翻去还是绕不开这道九键字母组合。作为深度优先遍历里最常用来“开场”的题目它的代码量不大但把递归、回溯、状态恢复这几个核心概念全占了非常适合用来讲清楚DFS到底在干什么。我索性把这几年反复写这道题、还有从它延伸出去的变种题目经验一并整理出来希望对正在刷题的人有帮助。1. 先搞清楚这道题到底在考什么1.1 题目本身的输入输出九键字母组合输入是一个只包含数字的字符串比如23输出要返回按顺序按下这些数字键时所有可能的字母组合。九宫格键盘的映射是这样规定的2对应abc3对应def4对应ghi5对应jkl6对应mno7对应pqrs8对应tuv9对应wxyz。注意7和9有4个字母其他按键是3个字母。输入23时最终结果应该是[ad, ae, af, bd, be, bf, cd, ce, cf]第一个数字2取一个字母第二个数字3取一个字母两个拼在一起就得到一个组合。数字串有多长组合出来的字符串长度就是多少。这道题的输出是“组合”而不是“排列”也就是说字母的位置是固定的第1位只能来自第1个按键第2位只能来自第2个按键。你不需要去把整个字符串重新洗牌也不需要考虑“ad”和“da”是不是两种。这一点决定了它的递归树长什么样也决定了写代码时索引参数的用法。1.2 为什么它天然是一棵递归树做这类题前我习惯先在脑子里把解空间画出来。按23为例第一位字母有3个分支每个分支下第二位又有3个分支所以总共有3 x 3 9个结果。如果把整个过程画出来就是一棵深度为2的树根节点是空字符串第一层有3个节点a、b、c第二层每个节点再分出3个子节点最终叶子节点数就是结果数DFS的含义就是从根出发沿着一条分支一直往下走走到叶子就记录一个结果然后回头走另一条分支。具体到这个题目就是先固定第一个字母为a然后分别拼上d、e、f再回头把第一个字母改成b继续分别拼上d、e、f。这样一棵树天然适合用递归来处理。因为每一层做的事完全一样从当前数字对应的字母表里挑一个字母拼到已有路径末尾然后去处理下一位数字。不同层之间唯一的区别是“当前处理到第几位”所以递归参数里只需要一个index就能区分层级。提示理解“每一层做同样的事、只靠参数区分状态”是看懂一切DFS递归代码的关键。看不懂代码时不要盯着每行死磕先试着把树的层级画出来代码就是树的翻译。2. 手把手写一个干净的DFS实现2.1 数字到字母的映射表怎么写映射关系通常有两种写法哈希表或者数组。这道题我用数组因为每个数字对应一个下标直接映射到字符串简单直接, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz数组前两个位置留空对应数字0和1。因为在老式九键键盘上0和1不参与字母映射下标占位后mapping[digits[index] - 0]就能拿到当前数字对应的字母串。不建议用switch或者一堆if/else去处理写起来啰嗦还容易漏分支。这里有个小细节经常被忽略字符0和整数0的ASCII码差了48。digits[index]是字符类型要拿到整数下标必须digits[index] - 0。我第一次写这道题时直接mapping[digits[index]]结果有时候取到空串有时候越界后来才意识到这是字符转整数的经典坑。2.2 递归函数的三要素参数设计DFS递归函数设计我通常按三件事来定参数当前处理到哪一层int index已经拼出的部分结果string path或ListCharacter path最终结果的收集容器result这三要素缺一不可。index决定递归何时终止path记录当前分支走到哪result是全局的收集器。终止条件写起来很自然index digits.length()说明所有数字都处理完了把path存进result。有人喜欢把index换成已处理字符串prefix比如递归参数传a、ab这样。好处是少一个索引参数坏处是每次递归都要创建一个新字符串内存开销大。刷题阶段我建议用索引加回溯这样能更好地理解DFS的状态恢复机制。还有一个决定代码风格的问题path用字符串拼还是用列表加回溯两种都对Python里字符串是不可变对象每次拼接都会生成新对象代码会简洁一些但递归深度大时开销明显。用列表的话最后join一次性能更好也逼着自己写出“先加入、递归、再撤销”的标准回溯三步。2.3 三种语言的完整实现对照不同语言写DFS风格差异集中在两点字符串或列表的传递方式、递归函数怎么访问外部变量。C实现我习惯把mapping和result写成成员变量递归函数少传两个参数class Solution { public: vectorstring letterCombinations(string digits) { if (digits.empty()) return {}; string path; backtrack(digits, 0, path); return result; } private: vectorstring mapping {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; vectorstring result; void backtrack(const string digits, int index, string path) { if (index digits.size()) { result.push_back(path); return; } string letters mapping[digits[index] - 0]; for (char c : letters) { path.push_back(c); backtrack(digits, index 1, path); path.pop_back(); } } };Python实现核心逻辑一样path用列表def letter_combinations(digits: str) - list[str]: if not digits: return [] mapping [, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz] result [] path [] def dfs(index: int) - None: if index len(digits): result.append(.join(path)) return for ch in mapping[int(digits[index])]: path.append(ch) dfs(index 1) path.pop() dfs(0) return resultJavaScript实现闭包写法最顺手const letterCombinations (digits) { if (!digits) return []; const mapping [, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz]; const result []; const path []; const dfs (index) { if (index digits.length) { result.push(path.join()); return; } for (const ch of mapping[Number(digits[index])]) { path.push(ch); dfs(index 1); path.pop(); } }; dfs(0); return result; };三个版本里最核心的动作都是同一个三部曲选一个字母放进路径递归处理下一位撤销刚才的选择。把path.pop_back()或者path.pop()去掉整个程序就会崩溃式地产生重复结果这一点在后面的避坑部分我会展开说。注意C里backtrack的path是引用传参递归返回后一定要pop_back()恢复现场。如果不用引用每次递归都拷贝一份path虽然逻辑上也能对但性能差一个数量级。3. 复杂度、迭代改法与几个实用优化3.1 时间空间复杂度到底怎么算先给结论时间复杂度和结果数量成正比空间复杂度等于递归栈深度加上结果存储。设输入数字串长度为n每个数字最多对应4个字母那么最多有4^n个结果。生成一个结果字符串需要 O(n) 的拼接拷贝时间所以最坏时间复杂度是 O(n * 4^n)。很多讲法只写 O(4^n)那是忽略了字符串拼接这一步。虽然常数因子不影响量级但面试被追问时能答出这个细节会加分。空间复杂度分两部分递归栈深度最大是 n这是 O(n)存储所有结果的列表是 O(4^n)。所以整体空间复杂度 O(4^n)。如果结果不计入复杂度那主要就是递归栈 O(n)。这里还有个可以提的观察点如果输入是9999每个按键4个字母结果是4^4 256个如果输入是23结果是3^2 9个。复杂度被字符集大小直接放大4的指数增长非常快。所以这道题没有真正意义上的“优化到多项式时间”的办法因为输出本身就那么大你不可能比输出结果更快。凡是说“优化到O(n)”的都是在耍流氓除非不要求返回所有组合。3.2 用队列改写从DFS到层序迭代DFS写熟了之后可以尝试用队列做一层一层的扩展这是这道题另一种经典解法。思路是维护一个队列初始放一个空字符串然后每读入一个数字就把队列里所有字符串取出来分别拼接这个数字对应的每个字母再放回队列。def letter_combinations_bfs(digits: str) - list[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这段代码每一轮循环处理一个数字处理完一轮队列里的字符串长度就加1。处理完所有数字队列里的每条字符串长度等于数字串长度也就是最终答案。这个过程等价于原始树的一层层遍历本质上就是BFS。我个人的看法是这道题DFS更直观因为“每个位置选一个字母”本身就是纵向深入的思路。BFS版本适合用来直观地感受回溯和最短路之间的关系但前提是题目允许“一层层生成”。如果在实际工程里输入数字串很长、需求只需要前几个结果时BFS配合队列截断反而更灵活比如只取前100条就停止DFS就得额外加计数器。3.3 缓存和预分配这类小优化九键字母组合本身没有太多优化空间但有几个小优化值得养成习惯C里在递归前先result.reserve(...)预先分配好大致的容量能减少字符串数组扩容带来的重复拷贝。容量的上下界是3^n到4^n可以直接按最大量预留。Python里path用列表而不是字符串拼接最后只join一次性能会好很多。字符串是不可变对象每次path ch都生成新字符串递归深了会产生大量临时对象。如果同一个数字串要被查询多次可以给mapping结果加一层缓存用字典记录已经算过的输入。比如cache {} def letter_combinations_with_cache(digits): if digits not in cache: cache[digits] letter_combinations(digits) return cache[digits]这个优化在刷题时通常用不上但如果你在做输入法联想、批量电话号码转文字这类业务相同的按键序列会被大量重复查询缓存收益非常明显。4. 从九键出发DFS的家族变种题4.1 变种题一组合总和与全排列九键字母组合解决的是“每个位置从有限的集合里选一个元素排列出所有结果”的问题。它几乎是回溯算法里最简单的一类没有约束条件没有重复元素只要填满每个位置就收集结果。一旦加上“不能重复选取”或者“元素可以重复但结果里不能有重复子集”的约束就变成了组合总和、全排列一类的题。比如全排列是在一个数字集合里选出所有排列和九键的区别在于九键每个位置的候选集是固定且互不干扰的全排列需要用一个visited数组标记哪些元素已经用过。代码结构上全排列的DFS多了一个“排除已用元素”的步骤撤销的时候除了pop_back()还要把visited状态重置。我见过很多人在九键这些基础题上练得不熟直接冲组合总和结果既分不清startIndex和index的区别也不知道什么时候用i1去避免重复。我的建议是先把九键这类“无选择的约束”写熟练再去加条件加一层约束就多一个参数思路不会乱。4.2 变种题二括号生成与恢复IP地址括号生成是DFS的经典进阶题它要求每层递归判断当前左括号和右括号的数量关系不再是“无脑选所有候选字母”。但骨架和九键一模一样先判断递归终点再遍历候选选择后递归递归结束撤销。恢复IP地址这类题目更有意思输入一个纯数字字符串要求分解成4段每段是0到255之间的数字输出所有合法IP。这题每一层要“选的长度”是可变的可能是1位、2位、3位所以在DFS内部多了一个for循环来枚举当前段截取的长度。本质上还是九键那棵树只是每个节点的分支数不固定而且每个分支要额外判断合法性。我把这些题和九键放在一起对比是因为它们共用同一个解题框架DFS函数里先判断终止条件然后枚举当前层所有可能的选择选择后递归调用调用回来撤销选择。框架本身不会变变的只是候选集合的大小、是否有限制条件、路径记录的格式。题目候选集来源是否可重复选额外约束九键字母组合数字对应的固定字母表每层独立无全排列输入数组的全部元素不可重复选需要 visited 标记组合总和输入数组的部分元素可以重复选需要用 startIndex 防止顺序重复括号生成左括号或右括号数量有限右括号数量不能超过左括号恢复IP地址每段截取1到3位数字每段独立段值必须合法4.3 一个业务化扩展带上词典过滤九键字母组合在真实场景里最常见的一个扩展是输入法联想和电话按键转文本。早期手机上输入英文单词连续按数字键系统要给出所有可能的字母组合再用上屏词典过滤最终留下真正是单词的候选。这个场景中全量枚举后过滤就行但如果数字串很长全量枚举的开销会承受不住所以更优的做法是在DFS的每一层就判断当前前缀是否存在于词典前缀树中如果不在就直接剪枝返回。这个优化思路也叫“前缀剪枝”。前面我说过九键没有可剪枝的约束条件但加上业务条件后情况就完全不同了。曾有一个项目里需要做关键词的模糊匹配输入一串数字把它转换成可能的字母组合再和已有词库比对。一开始全量枚举再过滤数字长度超过8就跑不动了后来改成DFS加前缀树剪枝组合数量在早期就被砍掉一大半后来数字长度到15也能秒出结果。这个例子说明一件事算法题里的“DFS”只是一个基础引擎真正决定性能的是你能不能根据业务约束在合适的位置让递归停下来。5. 我踩过的坑与排查技巧实录5.1 忘了回溯这一步结果直接翻倍最初写C版时我把递归调用的path.pop_back()漏了结果并非报错而是输出了一堆诡异的重复结果。比如输入23我得到的东西长度五花八门有的是两个字母有的是四个路径越攒越长递归完全失控。原因是没撤销时前面分支选过的字母全部留在了path里进入新分支时字符串会越来越长。回溯的作用就是把当前层加进去的字母撤掉让path回到进入递归前的状态。调试这类问题最直接的办法就是把递归函数里每次进入和返回时的path打印出来一眼就能看出哪一步没有恢复原状。记住这个底层逻辑path在递归里的角色是“当前路径”它只属于当前这层递归。你修改了它必须在返回前还原否则上层就看到一个被改过的路径。5.2 索引从0开始还是从1开始处理第几个数字时很多人会被index的起点带偏。我的写法是入口从dfs(0)开始递归里终止条件是index len(digits)所以一旦index等于长度就认定所有数字都处理完。如果入口写成dfs(1)终止条件就得是index len(digits)而且取数字时要digits[index - 1]容易出错。我建议统一用“0开头、等于长度终止”的约定这是C和Python等语言遍历容器最自然的方式。还有一处细节mapping[digits[index] - 0]很多人第一次写错成mapping[digits[index]]因为digits[index]是字符不是整数。Python里因为可以隐式转换字符串到整数反而不容易踩这个坑但 C 里字符的ASCII码会导致数组下表越界。刷题时如果用C遇到莫名越界先检查有没有做- 0。5.3 调试递归树的好习惯递归不好调是因为它跳来跳去不像循环那样线性推进。我的调试习惯是给DFS函数加一个depth参数然后在进入和退出时打印缩进def dfs(index: int, depth: int) - None: print( * depth fenter index{index}, path{path}) if index len(digits): result.append(.join(path)) print( * depth collect result, return) return for ch in mapping[int(digits[index])]: path.append(ch) dfs(index 1, depth 1) path.pop() print( * depth fbacktrack to index{index}, path{path})跑一次23你会看到类似这样的输出enter index0, path[] enter index1, path[a] enter index2, path[a, d] collect result, return enter index2, path[a, e] collect result, return ... backtrack to index1, path[a] enter index1, path[b] ...这样能直观看到DFS深挖到底、然后一层层弹回来的全过程。我在线下带人时经常用这个方式比讲十遍递归理论都管用。5.4 遇到的一些边界输入平时刷题九键这道题最容易出问题的输入是空字符串。标准预期是返回空列表而不是返回一个包含空字符串的列表。三种语言实现的入口都有if not digits或if (digits.empty())的判断先把这个边界处理掉后面递归才不会错乱。另一个边界是长度为1的输入比如2结果应该是[a, b, c]。这时递归只走一层恰好能验证index len(digits)的终止条件有没有写对。如果输出多了一个空字符串之类的内容说明入口的地方空字符串处理有误。还有23*这类输入题目一般说只含2到9的数字所以不用额外考虑*和#。但在业务里如果真的要处理特殊按键映射表里就要加对应的逻辑比如*可以映射成或者空字符这属于业务扩展不是题目考的点了。最后再分享一点我个人的体会九键字母组合这道题很多教程里都把它归为“简单题”但它的价值一点都不低。我面试别人或者带新人时经常用这道题来判断对方是不是真正理解了回溯代码背下来很容易但能讲清楚为什么要撤销、为什么复杂度是 O(n * 4^n)、为什么结果顺序是这样往往就不是一眼能看透的事了。建议拿到这道题时别急着写答案先动手把递归树画出来再思考每个叶子节点的路径是怎么一步步攒出来的。画通这一棵树后面所有DFS变种题的代码框架基本都不会再怵了。