一、题目描述给定一个仅包含数字29的字符串返回这些数字在电话按键上能够表示的所有字母组合答案顺序不限。数字和字母的对应关系如下2 - abc 3 - def 4 - ghi 5 - jkl 6 - mno 7 - pqrs 8 - tuv 9 - wxyz例如输入digits 23数字2可以选择a、b、c数字3可以选择d、e、f因此结果为[ad,ae,af,bd,be,bf,cd,ce,cf]这道题的关键不是按照某种规律计算字符串而是把每个数字对应的字母全部组合出来。只要题目要求“列出所有可能”通常就可以考虑 DFS 与回溯。二、核心思路把组合过程看成决策树假设输入为23整个选择过程可以看成一棵决策树。第 0 层处理数字2可以选择a、b、c第 1 层处理数字3可以选择d、e、f当处理完全部数字时就得到一个完整组合。例如先选择a再选择d得到ad回到上一层后撤销d再尝试e和f就能依次得到ae、af。因此每一层递归只需要完成三件事找到当前数字对应的字母集合依次选择其中一个字母并递归处理下一个数字递归返回后撤销刚才的选择继续尝试其他字母。这就是回溯的经典过程做出选择 - 进入下一层 - 撤销选择DFS 负责沿着一条路径不断向下搜索回溯则负责在一条路径搜索完成后恢复现场使程序能够继续探索其他分支。三、递归参数如何设计定义递归方法dfs(digits, index, path)三个参数的含义分别是digits原始数字字符串index当前正在处理第几个数字path当前已经选择的字母组合。例如输入23index 0处理数字 2 index 1处理数字 3 index 2所有数字处理完成所以递归终止条件为if (index digits.length()) { result.add(path.toString()); return; }当index等于数字字符串的长度时说明每个数字都已经选择了一个字母此时path就是一个完整答案。四、数字与字母的映射可以使用字符串数组保存电话按键映射private final String[] mapping { , , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz };数组下标直接对应数字。当前字符为digits.charAt(index)减去字符0后即可得到真正的数字下标String letters mapping[digits.charAt(index) - 0];例如字符3 - 0的结果是整数3因此可以得到mapping[3]也就是def。五、完整 Java 代码import java.util.ArrayList; import java.util.List; class Solution { private final ListString result new ArrayList(); private final String[] mapping { , , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz }; public ListString letterCombinations(String digits) { if (digits null || digits.length() 0) { return result; } dfs(digits, 0, new StringBuilder()); return result; } private void dfs(String digits, int index, StringBuilder path) { 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)); dfs(digits, index 1, path); path.deleteCharAt(path.length() - 1); } } }六、以23为例推演程序首先从index 0开始当前数字是2对应字母abc。第一次循环选择apath a随后递归到index 1处理数字3对应的def。依次选择d、e、f得到ad、ae、af生成ad后程序执行path.deleteCharAt(path.length() - 1);将d删除使path恢复为a然后才能继续选择e。数字3的所有字母处理完后递归返回第一层再删除a接着尝试b和c最终得到全部九种组合。整个过程可以概括为选择 a - 选择 d - 保存 ad - 删除 d - 选择 e - 保存 ae - 删除 e - 选择 f - 保存 af - 删除 f 删除 a继续选择 b、c七、为什么必须回溯StringBuilder是可变对象所有递归层操作的是同一个path。如果递归结束后不删除最后加入的字符旧路径就会影响后续分支。例如得到ad后如果不删除d下一次追加e就会变成ade而不是正确的ae。因此下面两行必须成对出现path.append(letters.charAt(i)); path.deleteCharAt(path.length() - 1);前者表示做出选择后者表示撤销选择。回溯不是重新创建一套状态而是在递归返回时把共享状态恢复到进入当前分支之前的样子。另外将答案加入结果集时需要调用path.toString()保存当前组合对应的字符串而不是保存可继续变化的构造器对象。八、复杂度分析数字7和9各对应 4 个字母其他数字对应 3 个字母。若输入长度为n组合数量最多为4^n。时间复杂度最坏为O(n × 4^n)。一共最多生成4^n个组合每个组合转换为字符串需要O(n)空间复杂度不计算返回结果时为O(n)主要来自递归栈和StringBuilder如果计算结果集则需要O(n × 4^n)。九、常见错误1. 空字符串返回包含空串的集合当输入为时题目要求返回空列表因此应在启动 DFS 前单独判断不能让递归直接把空字符串加入结果集。2. 递归时没有让index 1每层递归处理一个数字。若仍传入原来的index程序会反复处理同一数字无法正确终止。3. 忘记删除最后一个字符这是最常见的错误。每次递归返回后都要撤销当前层刚刚追加的字符保证同层不同分支互不影响。4. 使用组合长度代替索引却混淆含义本题中组合长度通常等于当前层数但直接使用index表达“正在处理哪个数字”更清晰也更不容易写错。十、总结这道题是 DFS 回溯的典型入门题。每个数字对应决策树的一层每个字母对应当前层的一种选择先把字母加入路径再递归处理下一个数字递归返回后删除刚加入的字母。当index digits.length()时说明已经走到叶子节点可以保存一个完整组合。