电话号码字母组合回溯解法详解（Python，Java解法）

题目给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。示例 1输入digits 23输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2输入digits 2输出[a,b,c]Python解法代码展示class Solution: def letterCombinations(self, digits: str) - List[str]: if not digits or len(digits) 0: return [] PHONE_MAP { 2:abc, 3:def, 4:ghi, 5:jkl, 6:mno, 7:pqrs, 8:tuv, 9:wxyz } n len(digits) res [] current [] * n def backtrack(index: int)-None: if index n: res.append(.join(current)) return for char in PHONE_MAP[digits[index]]: current[index] char backtrack(index 1) backtrack(0) return res解释1空值检查if not digits or len(digits) 0: return []2建立映射表PHONE_MAP { 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz }3进行初始化n len(digits) # 假设 digits 23, 则 n 2 result [] # 最终结果如 [ad,ae,af,bd,be,bf,cd,ce,cf] current [] * n # 预分配: [, ]固定长度为24函数终止条件if index n: result.append(.join(current)) return5递归循环核心逻辑for char in PHONE_MAP[digits[index]]: current[index] char # ① 做选择放字母 backtrack(index 1) # ② 进入下一层递归 # ③ 隐式回溯下次循环直接覆盖无需清理6启动与返回backtrack(0) # 从第0个数字开始 return result # 返回所有组合7.以23为例展示流程图Java解法代码示例解释在代码里public class Solution { // 类常量数字到字母的映射避免每次创建 private static final String[] PHONE_MAP { , // 索引0占位数字从2开始 , // 索引1占位 abc, // 索引2 → 数字2 def, // 索引3 → 数字3 ghi, // 索引4 → 数字4 jkl, // 索引5 → 数字5 mno, // 索引6 → 数字6 pqrs, // 索引7 → 数字7 tuv, // 索引8 → 数字8 wxyz // 索引9 → 数字9 }; public ListString letterCombinations(String digits) { // 第1步空值检查 if (digits null || digits.length() 0) { return new ArrayList(); // 返回空列表不是null } // 第2步初始化变量 int n digits.length(); // 数字字符串长度 ListString result new ArrayList(); // 存储所有最终组合 char[] current new char[n]; // 【关键优化】预分配字符数组 // Java的char数组默认初始化\0我们需要填充占位符便于调试 // 实际不需要填充直接覆盖即可 // 第3步启动回溯 backtrack(digits, 0, current, result); return result; } /** * 回溯函数 * param digits 输入的数字字符串 * param index 当前处理的数字位置 * param current 当前构建的字符数组预分配 * param result 最终结果列表 */ private void backtrack(String digits, int index, char[] current, ListString result) { // 第4步终止条件 if (index digits.length()) { // 将字符数组转换为字符串加入结果 result.add(new String(current)); return; } // 第5步获取当前数字对应的字母 char digitChar digits.charAt(index); // 如 2 int digit digitChar - 0; // 转换为数字 2 String letters PHONE_MAP[digit]; // 获取 abc // 第6步遍历所有字母递归处理 for (int i 0; i letters.length(); i) { char letter letters.charAt(i); // 如 a, b, c current[index] letter; // ① 做选择放置字母 backtrack(digits, index 1, current, result); // ② 进入下一层 // ③ 隐式回溯下次循环直接覆盖无需显式清理 } }总结本题主要运用了回溯方法属于全排列类回溯无去重无剪枝直接穷举处理完之后直接保存结果。