题目描述给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。数字到字母的映射与电话按键相同1 不对应任何字母。数字23456789字母abcdefghijklmnopqrstuvwxyz示例 1输入digits 23 输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2输入digits 输出[]示例 3输入digits 2 输出[a,b,c]提示1 digits.length 4digits[i] 是范围 [‘2’, ‘9’] 的一个数字解题思路总览方法对比方法时间复杂度空间复杂度实现难度推荐指数回溯DFSO(4^n)O(n)简单⭐⭐⭐⭐⭐BFS 队列O(4^n)O(4^n)中等⭐⭐⭐⭐迭代拼接O(4^n)O(4^n)简单⭐⭐⭐⭐为什么回溯是最佳选择这是一道典型的「决策树」问题。对于输入 “23”第一个数字 2 有 3 种选择a, b, c第二个数字 3 有 3 种选择d, e, f所有组合 3 × 3 9 种回溯法正好能天然地遍历这棵决策树代码简洁清晰。完整代码方法一回溯DFSclassSolution{public:vectorstringletterCombinations(string digits){if(digits.empty())return{};vectorstringhash{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};string path;vectorstringans;autotraversal[](autoself,intindex)-void{if(path.size()digits.size()){ans.push_back(path);return;}string lettershash[digits[index]-0];for(charch:letters){path.push_back(ch);self(self,index1);path.pop_back();}};traversal(traversal,0);returnans;}};方法二BFS 队列classSolution{public:vectorstringletterCombinations(string digits){if(digits.empty())return{};vectorstringhash{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};vectorstringans{};for(chardigit:digits){vectorstringtemp;for(string s:ans){for(charch:hash[digit-0]){temp.push_back(sch);}}ans.swap(temp);}returnans;}};算法流程图回溯法[开始] | [检查空字符串] | / 是 \ / 否 / \ 返回 [] [初始化] | [递归 traversal(0)] | [path.size() n?] | / 是 \ / 否 / \ 保存结果 [获取letters] 返回 | [遍历 letters] | ---------------- | | [pathch] [递归 traversal(index1)] | | [path.pop] [继续遍历下一个字符] | | ----[循环结束]--- | [返回结果]决策树图解以 “23” 为例[根节点] | ------------------ | | | a b c - 第一层2的3种选择 | | | --------- --------- --------- | | | | | | | | | ad ae af bd be bf cd ce cf | 第二层3的3种选择每个节点分叉3个总组合数3 × 3 9 种逐行解析1. 边界处理if(digits.empty())return{};如果输入为空字符串直接返回空vector这是递归函数的重要出口避免后续访问空字符串2. 建立映射表vectorstringhash{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};用数组下标 0-9 建立数字到字母的映射0 和 1 对应空字符串题目说1不对应任何字母下标 2-9 对应实际字母3. Lambda 递归定义autotraversal[](autoself,intindex)-void{auto self是完美转发让 lambda 能够调用自身index表示当前正在处理第几个数字从0开始4. 终止条件if(path.size()digits.size()){ans.push_back(path);return;}当 path 长度等于 digits 长度说明所有数字都处理完了此时得到一个完整组合存入结果集5. 核心回溯逻辑string lettershash[digits[index]-0];for(charch:letters){path.push_back(ch);// 做选择self(self,index1);// 递归处理下一个数字path.pop_back();// 撤销选择}digits[index] - 0将字符’2’-9’转为整数2-9遍历当前数字对应的每个字母对每个字母执行选择 → 递归 → 撤销详细 trace 演示以输入 “23” 为例跟踪执行过程初始状态 path index 0 ans [] 第0层处理数字2 letters abc 选择 a path a 进入第1层处理数字3 letters def 选择 dpath ad已满ans [ad] 选择 epath ae已满ans [ad, ae] 选择 fpath af已满ans [ad, ae, af] 回溯到第0层path恢复为 选择 b path b 进入第1层... ans [ad, ae, af, bd, be, bf] 回溯path恢复为 选择 c path c 进入第1层... ans [ad, ae, af, bd, be, bf, cd, ce, cf] 最终返回[ad,ae,af,bd,be,bf,cd,ce,cf]复杂度分析时间复杂度O(4^n)n的值最大组合数说明132 或 3 或 4 …293 × 33273 × 3 × 34813 × 3 × 3 × 3最坏情况全用7或9每个数字最多对应 4 个字母7: pqrs, 9: wxyz最坏情况所有数字都是 7 或 9总组合数 4 × 4 × … × 4 4^n空间复杂度O(n)组成部分占用空间说明递归栈O(n)最多递归n层path字符串O(n)存储当前路径hash映射表O(1)大小固定注不计输出结果 ans 本身占用的空间常见错误与修正错误写法谨慎// 错误index 参数使用不当autotraversal[](autoself,intindex)-void{if(digits.size()path.size()){ans.push_back(path);return;}for(intiindex;idigits.size();i){// 错误外层循环变量ifor(charch:hash[digits[i]-0]){// 错误用i而非indexpath.push_back(ch);self(self,i1);// 错误传的是 i1 而不是 index1path.pop_back();}}};问题分析外层循环i从index开始导致重复处理同一个位置的数字传入i 1而非index 1破坏了递归的单调性正确写法autotraversal[](autoself,intindex)-void{if(path.size()digits.size()){ans.push_back(path);return;}string lettershash[digits[index]-0];// 正确用 index 获取当前数字for(charch:letters){path.push_back(ch);self(self,index1);// 正确传 index1path.pop_back();}};面试追问 FAQ问题参考答案为什么用回溯而不是循环回溯天然适合「每个位置有多个选择」的问题能清晰地表达决策树的遍历过程如何保证结果不重复本题天然无重复因为每个数字对应唯一字母集合不存在选择重复的问题能并行处理吗可以将不同分支分配到不同线程但需要注意结果合并意义不大递归改迭代怎么做用循环从左到右处理每个数字两两合并结果集BFS方法n很大时结果太多怎么办组合数指数增长考虑限制输出数量、分批处理或返回迭代器如何做到按字典序输出在hash表中按字母顺序遍历自然得到字典序结果空间优化怎么做可以用string的push_back/pop_back原地修改避免复制相关题目对比题目难度核心区别关键点22. 括号生成中等生成合法括号组合需要判断合法性左括号右括号39. 组合总和中等可以重复选择同一数字candidates中的数字可以重复使用40. 组合总和 II中等每个数字只能选一次需要去重使用used数组标记46. 全排列中等所有数字不重复需要used数组标记已使用77. 组合中等从n个数中选k个start参数控制起始位置79. 单词搜索中等二维矩阵回溯需要标记已访问回退时恢复131. 分割回文串中等分割字符串需要判断回文递归深入216. 组合总和 III中等选k个数求和为n限制组合长度和目标值变形题目变形1限制结果数量题目返回前k个组合k 100思路回溯时计数器达到k就提前返回vectorstringans;intcount0;voidbacktrack(...){if(countk)return;if(path.size()n){ans.push_back(path);count;return;}// ...}变形2带权重的随机组合题目每个数字对应的字母有权重返回按权重概率分布的组合思路预处理时根据权重展开字母串变形3返回编号而非字母题目返回组合对应的数字编号如 “23→23”, “ad→23”思路收集过程中直接记录数字字符举一反三什么时候用回溯问题的解空间是树状结构每个节点有多个分支选择需要枚举所有可能的解回溯三部曲1. 出口条件 - 找到完整解 or 超出限制 2. 做选择 - 将当前选择加入路径 3. 递归 - 深入下一层 4. 撤销 - 回退恢复状态回溯 vs 深搜 vs 递归概念侧重点递归思想强调自己调用自己深搜DFS图论强调遍历顺序回溯应用强调「选择-撤销」的模式总结要点内容数据结构数组建立映射表核心算法回溯选择 → 递归 → 撤销时间复杂度O(4^n)空间复杂度O(n)关键点1边界条件处理空字符串关键点2字符转数字下标digit - 0关键点3回溯三步曲选、递归、撤销变形方向限制数量、权重随机、返回编号完整测试代码#includeiostream#includevector#includestringusingnamespacestd;classSolution{public:vectorstringletterCombinations(string digits){if(digits.empty())return{};vectorstringhash{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};string path;vectorstringans;autotraversal[](autoself,intindex)-void{if(path.size()digits.size()){ans.push_back(path);return;}string lettershash[digits[index]-0];for(charch:letters){path.push_back(ch);self(self,index1);path.pop_back();}};traversal(traversal,0);returnans;}};// 测试intmain(){Solution s;vectorstringtest{23,2,};for(string digits:test){cout输入: \digits\endl;cout输出: [;vectorstringanss.letterCombinations(digits);for(inti0;ians.size();i){cout\ans[i]\;if(ians.size()-1)cout, ;}cout]endlendl;}return0;}运行结果输入: 23 输出: [ad, ae, af, bd, be, bf, cd, ce, cf] 输入: 2 输出: [a, b, c] 输入: 输出: []
