LeetCode中等难度题目——17. 电话号码的字母组合这道题是回溯算法的经典入门题既能帮我们熟悉回溯的核心思想又能巩固字符串、哈希表的基础用法非常适合新手上手练习。一、题目解析读懂需求明确边界先看题目要求给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合答案可以按任意顺序返回。核心映射关系和手机按键一致2 → abc3 → def4 → ghi5 → jkl6 → mno7 → pqrs8 → tuv9 → wxyz关键边界条件输入为空字符串digits.length 0时直接返回空数组数字仅包含2-9无需处理11不对应任何字母输出需包含所有可能的组合无重复、无遗漏。举个例子输入 “23”输出应该是 [“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]因为2对应abc3对应def每个字母两两组合就是所有可能的结果。二、解题思路为什么选回溯算法这道题的核心是「穷举所有可能的组合」而回溯算法正是解决「穷举组合」类问题的最优思路之一。什么是回溯简单来说就是「走一步、试一步走不通就退回来换条路走」本质是一种深度优先搜索DFS只不过在搜索过程中会「回溯」到上一步继续尝试其他可能性。对应这道题我们可以这样理解先取第一个数字对应的所有字母逐个选择一个字母作为组合的第一个字符再取第二个数字对应的所有字母逐个拼接在第一个字符后面作为组合的第二个字符以此类推直到拼接的字符长度等于输入数字的长度说明已经处理完所有数字就把这个组合加入结果集当一个数字的所有字母都尝试完就回溯到上一个数字换一个字母继续拼接直到所有可能性都被尝试完。举个通俗的例子输入 “23”流程就是a→d加入结果→a→e加入结果→a→f加入结果→回溯到aa的所有字母尝试完回溯到2换b→b→d加入结果→b→e加入结果…… 以此类推直到所有组合都被生成。三、完整代码实现TypeScript下面是完整的解题代码注释已经写得非常详细大家可以先通读一遍后续逐句拆解functionletterCombinations(digits:string):string[]{// 边界条件输入为空直接返回空数组if(digits.length0)return[];// 建立数字到字母的映射表用Map存储查询更高效constmapnewMap([[2,abc],[3,def],[4,ghi],[5,jkl],[6,mno],[7,pqrs],[8,tuv],[9,wxyz]]);// 存储最终结果的数组constresult:string[][];// 输入数字串的长度用于判断终止条件constdigitsLen:numberdigits.length;/** * 回溯函数递归生成字母组合 * param {number} index - 当前处理的数字在digits中的索引 * param {string} currentStr - 当前已经拼接好的字母组合 * returns */constbacktrack(index:number,currentStr:string){// 终止条件当处理完所有数字索引等于数字串长度将当前组合加入结果集if(indexdigitsLen){result.push(currentStr);return;}// 取出当前数字对应的字母加非空判断增强代码健壮性避免异常constlettersmap.get(digits[index]);if(!letters)return;// 遍历当前数字对应的每一个字母递归拼接letters.split().forEach((letter:string){// 字符串不可变currentStr letter 会生成新字符串无需手动回溯天然回溯backtrack(index1,currentStrletter);});}// 启动回溯从第0个数字开始初始拼接字符串为空backtrack(0,);// 返回最终结果returnresult;};四、代码逐句拆解读懂每一步的意义1. 边界条件处理if (digits.length 0) return [];这一步很关键当输入为空字符串时没有任何组合可以生成直接返回空数组避免后续递归报错。2. 建立数字-字母映射用Map存储映射关系相比对象ObjectMap的get方法查询效率更高而且可以直接用数组初始化代码更简洁。这里明确了每个数字对应的字母和题目要求完全一致。3. 初始化变量result: string[] []用于存储所有生成的字母组合最终作为返回值digitsLen: number digits.length存储输入数字串的长度避免在递归中多次调用digits.length提升性能虽然影响不大但养成良好习惯。4. 核心回溯函数backtrack回溯函数是这道题的灵魂我们重点拆解它的两个参数和内部逻辑参数说明index: number当前正在处理的数字在digits中的索引比如输入23index0时处理数字2index1时处理数字3currentStr: string当前已经拼接好的字母组合比如index0时currentStr可能是a、“b”、“c”index1时currentStr可能是ad、ae等。终止条件if (index digitsLen) { result.push(currentStr); return; }当index等于数字串的长度时说明我们已经处理完了所有数字当前的currentStr就是一个完整的组合把它加入result然后返回结束当前递归回溯到上一步。获取当前数字对应的字母const letters map.get(digits[index]); if (!letters) return;根据当前index取出digits中对应的数字再通过Map获取该数字对应的字母串。加一个非空判断防止出现异常虽然题目说输入仅包含2-9但健壮性代码不能少。遍历字母递归拼接letters.split().forEach((letter: string) { backtrack(index 1, currentStr letter); });这一步是回溯的核心逻辑将字母串拆分成单个字母比如abc拆成[“a”,“b”,“c”]遍历每个字母调用回溯函数此时index1处理下一个数字currentStrletter将当前字母拼接到已有的组合上这里有个小技巧因为字符串是不可变的currentStr letter会生成一个新的字符串而不是修改原字符串所以当递归结束后会自动回到上一步的currentStr无需手动“回溯”比如拼接完ad递归结束后会回到a继续拼接ae。5. 启动回溯backtrack(0, );从第一个数字index0开始初始的拼接字符串为空启动递归流程开始生成所有组合。五、易错点提醒 优化方向易错点忘记处理输入为空的情况导致递归报错回溯函数的终止条件写错比如写成index digitsLen导致组合缺失或重复没有加非空判断if (!letters) return虽然题目输入合法但代码不够健壮混淆index的含义导致处理数字时出现偏差。优化方向这道题的解法已经很高效了但可以做一些小优化提升可读性和性能用数组代替Map存储映射关系比如const map [, , abc, def, ...]通过索引直接获取数字字符转数字即可比如digits[index] - 0查询速度更快用数组拼接代替字符串拼接因为字符串不可变频繁拼接会生成新字符串数组pushjoin效率更高比如用currentArr存储当前组合递归时push(letter)回溯时pop()最后join成字符串加入结果集。优化后的回溯函数数组拼接版constbacktrack(index:number,currentArr:string[]){if(indexdigitsLen){result.push(currentArr.join());return;}constlettersmap.get(digits[index]);if(!letters)return;letters.split().forEach(letter{currentArr.push(letter);// 加入当前字母backtrack(index1,currentArr);currentArr.pop();// 回溯移除最后一个字母});}// 启动回溯backtrack(0,[]);六、总结回溯算法的核心要点通过这道题我们可以总结出回溯算法解决组合问题的通用步骤确定「终止条件」当满足某个条件比如处理完所有元素将当前结果加入结果集返回确定「递归逻辑」遍历当前可选的所有元素逐个选择递归处理下一个元素「回溯操作」要么利用不可变类型如字符串天然回溯要么手动回溯如数组pop()回到上一步继续尝试。这道题作为回溯入门题难度适中理解透彻后再去做LeetCode上其他回溯题目比如组合总和、子集会轻松很多。