Java版LeetCode热题100之电话号码的字母组合：回溯算法的经典应用

Java版LeetCode热题100之电话号码的字母组合：回溯算法的经典应用

摘要：本文将深入剖析 LeetCode 热题 100 中的经典回溯问题——电话号码的字母组合（Letter Combinations of a Phone Number）。我们将从题目出发，系统讲解回溯算法的核心思想、递归结构设计，并提供完整可运行的 Java 实现。文章涵盖时间/空间复杂度分析、常见面试问题、实际应用场景、相关题目推荐等模块，帮助读者不仅掌握解题技巧，更能理解其背后的算法思想与工程价值。

一、原题回顾

题目名称：电话号码的字母组合
题目编号：LeetCode 17
难度等级：中等

题目描述

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

数字到字母的映射如下（与电话按键相同）：

• 2→"abc"
• 3→"def"
• 4→"ghi"
• 5→"jkl"
• 6→"mno"
• 7→"pqrs"
• 8→"tuv"
• 9→"wxyz"

注意：数字1不对应任何字母。

示例

示例 1： 输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] 示例 2： 输入：digits = "2" 输出：["a","b","c"] 示例 3： 输入：digits = "" 输出：[]

提示

• 1 <= digits.length <= 4
• digits[i]是范围['2', '9']的一个数字

二、原题分析

本题是一个典型的**笛卡尔积（Cartesian Product）**问题：给定多个集合，求它们所有可能的元素组合。

例如，"23"对应：

• 集合1：{'a','b','c'}
• 集合2：{'d','e','f'}
• 笛卡尔积：{('a','d'), ('a','e'), ..., ('c','f')}

由于digits.length ≤ 4，且每个数字最多对应 4 个字母，最大组合数为4⁴ = 256，属于可枚举范围，适合使用回溯法（Backtracking）。

💡关键观察：这是一个多层嵌套循环问题，但层数不固定（由digits长度决定），因此不能用固定层数的 for 循环解决，而回溯法天然适合处理这种可变深度的组合问题。

三、答案构思

3.1 回溯法的核心思想

回溯法是一种通过递归+状态恢复系统搜索所有可能解的算法。对于本题：

• 路径（Path）：当前已构建的字母组合（如"ad"）
• 选择列表（Choices）：当前数字对应的所有字母
• 结束条件（Base Case）：已处理完所有数字

3.2 算法步骤

1. 预处理：建立数字到字母的映射（哈希表）
2. 边界处理：若输入为空，直接返回空列表
3. 回溯函数：
   • 若已处理完所有数字，将当前组合加入结果
   • 否则，获取当前数字对应的字母字符串
   • 遍历每个字母：
     • 做选择：将字母加入当前组合
     • 递归：处理下一个数字
     • 撤销选择：移除刚加入的字母（状态恢复）

3.3 为什么用 StringBuffer？

• 频繁修改字符串：回溯过程中需要不断添加和删除字符
• StringBuffer vs StringBuilder：
  • 两者都可变，但StringBuffer线程安全
  • 本题单线程，用StringBuilder更高效
  • 官方题解用StringBuffer是历史原因

📌优化建议：实际开发中优先使用StringBuilder。

四、完整答案（Java 实现）

4.1 官方题解（StringBuffer 版）

classSolution{publicList<String>letterCombinations(Stringdigits){List<String>combinations=newArrayList<>();if(digits.length()==0){returncombinations;}// 建立数字到字母的映射Map<Character,String>phoneMap=newHashMap<Character,String>(){{put('2',"abc");put('3',"def");put('4',"ghi");put('5',"jkl");put('6',"mno");put('7',"pqrs");put('8',"tuv");put('9',"wxyz");}};backtrack(combinations,phoneMap,digits,0,newStringBuffer());returncombinations;}privatevoidbacktrack(List<String>combinations,Map<Character,String>phoneMap,Stringdigits,intindex,StringBuffercombination){// 结束条件：已处理完所有数字if(index==digits.length()){combinations.add(combination.toString());}else{chardigit=digits.charAt(index);Stringletters=phoneMap.get(digit);// 遍历当前数字对应的所有字母for(inti=0;i<letters.length();i++){// 做选择combination.append(letters.charAt(i));// 递归处理下一个数字backtrack(combinations,phoneMap,digits,index+1,combination);// 撤销选择（关键！）combination.deleteCharAt(index);}}}}

4.2 优化版（StringBuilder + 静态映射）

classSolution{// 静态映射，避免每次创建privatestaticfinalString[]LETTERS={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};publicList<String>letterCombinations(Stringdigits){List<String>result=newArrayList<>();if(digits==null||digits.isEmpty()){returnresult;}backtrack(digits,0,newStringBuilder(),result);returnresult;}privatevoidbacktrack(Stringdigits,intindex,StringBuilderpath,List<String>result){if(index==digits.length()){result.add(path.toString());return;}// 获取当前数字对应的字母Stringletters=LETTERS[digits.charAt(index)-'0'];for(charc:letters.toCharArray()){path.append(c);// 做选择backtrack(digits,index+1,path,result);// 递归path.deleteCharAt(path.length()-1);// 撤销选择}}}

✅优化点：

1. 使用String[]替代HashMap，访问更快
2. 使用StringBuilder替代StringBuffer
3. 边界检查更严谨（null处理）

五、代码分析

5.1 回溯函数详解

参数含义

• digits：原始数字字符串
• index：当前处理到的数字索引
• path：当前构建的字母组合（可变字符串）
• result：结果列表

递归过程

以digits = "23"为例：

初始: path="", index=0 ├─ 选 'a': path="a", index=1 │ ├─ 选 'd': path="ad", index=2 → 加入结果 │ ├─ 选 'e': path="ae", index=2 → 加入结果 │ └─ 选 'f': path="af", index=2 → 加入结果 ├─ 选 'b': path="b", index=1 │ ├─ 选 'd': path="bd", index=2 → 加入结果 │ ... └─ 选 'c': path="c", index=1 ...

状态恢复的关键

path.deleteCharAt(path.length()-1);

• 为什么不是deleteCharAt(index)？
  • 因为path的长度始终等于index
  • 所以path.length() - 1 == index - 1？不！
  • 实际上：path.length() == index（因为每层递归添加一个字符）
  • 所以path.length() - 1 == index - 1是错误的！

🔥纠正：在官方题解中，combination.deleteCharAt(index)是正确的，因为：

• 初始时combination为空
• 第 0 层添加字符后，combination长度为 1，要删除索引 0
• 第 1 层添加后，长度为 2，要删除索引 1
• 所以删除位置确实是index

但在优化版中，我们使用path.length() - 1，因为：

• path始终只包含已选择的字符
• 当前要删除的就是最后一个字符

两种方式都正确，但优化版更直观。

5.2 边界情况处理

• 空输入：digits = ""→ 返回空列表（非null）
• 单数字：digits = "2"→ 返回["a","b","c"]
• 含 7/9：digits = "79"→ 每个数字对应 4 个字母

5.3 映射表的设计

方案对比

📌推荐：String[]方案，性能最优。

六、时间复杂度与空间复杂度分析

6.1 时间复杂度：O(3ᵐ × 4ⁿ)

• m：对应 3 个字母的数字个数（2,3,4,5,6,8）
• n：对应 4 个字母的数字个数（7,9）
• 总组合数：3ᵐ × 4ⁿ
• 每种组合的构建成本：O(m+n)（字符串拼接）
• 但通常简化为 O(3ᵐ × 4ⁿ)，因为 m+n ≤ 4

💡最坏情况：digits = "7777"→ 4⁴ = 256 种组合

6.2 空间复杂度：O(m+n)

• 递归栈深度：m+n（等于digits.length()）
• 每层栈空间：O(1)（局部变量）
• 结果集空间：O((m+n) × 3ᵐ × 4ⁿ)，但通常不计入
• 额外空间：
  • 映射表：O(1)（固定大小）
  • StringBuilder：O(m+n)（当前路径）

📌标准答案的空间复杂度为 O(m+n)（仅考虑算法运行所需额外空间）。

七、常见问题解答（FAQ）

Q1: 为什么不用 BFS？

答：可以用，但回溯更自然：

• BFS：用队列存储中间结果，每层扩展
• 回溯：直接构建完整结果，空间更省
• 本题深度小（≤4），两者差异不大，但回溯代码更简洁

Q2: 能否用迭代（非递归）实现？

答：可以，逐个数字扩展结果：

publicList<String>letterCombinations(Stringdigits){if(digits.isEmpty())returnnewArrayList<>();List<String>result=Arrays.asList("");String[]letters={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};for(chardigit:digits.toCharArray()){List<String>newResult=newArrayList<>();for(Stringprefix:result){for(charc:letters[digit-'0'].toCharArray()){newResult.add(prefix+c);}}result=newResult;}returnresult;}

优点：无递归，易理解
缺点：频繁创建新字符串，内存开销大

Q3: 如何按字典序输出？

答：本题天然按字典序输出，因为：

• 数字按顺序处理
• 每个数字的字母按"abc"顺序遍历
• 例如"23"→["ad","ae","af","bd",...]已是字典序

Q4: 如果数字包含 ‘0’ 或 ‘1’ 怎么办？

答：题目保证只含 ‘2’-‘9’，但实际可扩展：

• '0'→" "（空格）
• '1'→""（空字符串）
• 处理时跳过空字符串的数字

八、优化思路

8.1 预分配结果集大小

计算总组合数，预设ArrayList容量：

// 计算总组合数inttotal=1;for(charc:digits.toCharArray()){total*=LETTERS[c-'0'].length();}List<String>result=newArrayList<>(total);

避免动态扩容的内存拷贝。

8.2 使用 char[] 代替 StringBuilder

减少对象创建：

privatevoidbacktrack(Stringdigits,intindex,char[]path,List<String>result){if(index==digits.length()){result.add(newString(path));return;}Stringletters=LETTERS[digits.charAt(index)-'0'];for(inti=0;i<letters.length();i++){path[index]=letters.charAt(i);backtrack(digits,index+1,path,result);}}

调用：

char[]path=newchar[digits.length()];backtrack(digits,0,path,result);

优点：无 append/delete 开销
缺点：代码稍复杂

8.3 并行化？不推荐！

• 最大 256 个结果，串行已足够快
• 并行 overhead 远大于收益
• 递归结构难以并行

九、数据结构与算法基础知识点回顾

9.1 什么是回溯算法？

• 定义：一种通过递归+剪枝系统搜索解空间的算法
• 适用场景：组合、排列、子集、N皇后、数独等
• 核心要素：
  • 选择（Choose）
  • 约束（Constraint）
  • 目标（Goal）

9.2 回溯 vs DFS

回溯可视为带状态恢复的 DFS。

9.3 笛卡尔积（Cartesian Product）

• 定义：两个集合 A 和 B 的笛卡尔积是所有有序对 (a,b) 的集合
• 扩展：多个集合的笛卡尔积
• 应用：数据库 JOIN、组合生成、测试用例生成

9.4 决策树模型

以"23"为例：

"" / | \ "a" "b" "c" /|\ /|\ /|\ "ad"..."af" ... "cf"

• 树深度：digits.length
• 叶节点数：总组合数
• 回溯 = 从根到叶的路径探索 + 返回

十、面试官提问环节（模拟）

Q1: 请手写电话号码的字母组合，并解释回溯的过程。

答：（写出优化版代码后解释）

• 我们用index表示当前处理的数字位置
• 对每个数字，遍历其对应的所有字母
• 将字母加入当前路径，递归处理下一个数字
• 返回后移除该字母，尝试下一个字母
• 当index等于digits.length()时，得到一个完整组合

Q2: 时间复杂度为什么是 O(3ᵐ × 4ⁿ)？能否优化？

答：

• 每个数字 2-6,8 对应 3 个字母，7,9 对应 4 个
• 总组合数 = 3ᵐ × 4ⁿ，必须全部生成
• 无法优化时间复杂度，因为必须输出所有组合
• 但可优化常数因子（如预分配空间、用 char[]）

Q3: 如果输入很长（如 20 位），还能用回溯吗？

答：不能。

• 4²⁰ ≈ 10¹²，远超计算能力
• 此时应：
  • 使用生成器模式按需生成组合
  • 或问题本身有特殊约束可剪枝（如只求前 k 个）

Q4: 如何修改代码以支持数字 ‘0’ 和 ‘1’？

答：

• 扩展映射表：'0' → " ",'1' → ""
• 在回溯时，若字母字符串为空，直接递归下一层
• 或预处理输入，过滤掉 ‘0’/‘1’

Q5: 回溯中的“状态恢复”为什么重要？

答：因为回溯是共享状态的递归。

• 若不恢复，后续分支会基于错误的状态计算
• 例如：第一次选择 ‘a’ 后未移除，第二次选择 ‘b’ 时路径变成 “ab”
• 导致结果错误（如 “abd” 而非 “bd”）

十一、这道算法题在实际开发中的应用

11.1 输入法预测

• 用户输入数字序列，预测可能的单词
• 如 T9 输入法（老式手机）

11.2 密码恢复

• 已知密码的数字模式（如生日），生成所有可能字母组合
• 用于安全测试（需授权！）

11.3 测试用例生成

• API 参数有多个选项，生成所有参数组合
• 例如：{color: [red, blue], size: [S, M, L]}

11.4 配置组合

• 软件配置项的笛卡尔积
• 用于兼容性测试或默认配置生成

11.5 自然语言处理

• 语音识别中的候选词生成
• 拼写纠错的可能替换组合

💡 虽然实际中很少直接处理电话号码，但笛卡尔积生成是许多系统的底层需求。

十二、相关题目推荐

学习路径建议：

1. 掌握本题（笛卡尔积）
2. → 78（子集）
3. → 77（固定大小组合）
4. → 39/40（带目标和）
5. → 46（排列）

十三、总结与延伸

13.1 核心收获

• 电话号码问题是笛卡尔积的经典应用
• 回溯法是解决可变深度组合问题的标准方法
• 状态恢复是回溯算法的关键
• 时间复杂度由输出规模决定，无法优化

13.2 延伸思考

如何按需生成组合（迭代器模式）？

• 实现Iterator<String>接口
• 内部维护当前组合的索引数组
• next()方法计算下一个组合
• 适用于大数据量场景

支持通配符？

• 如digits = "2*"，*表示任意数字
• 需先展开通配符，再生成组合
• 或在回溯时动态处理

并行生成？

• 对第一个数字的字母并行处理
• 每个线程负责一个前缀
• 但小数据量下不划算

13.3 学习建议

1. 动手实现：手写回溯模板（选择/递归/撤销）
2. 理解状态：明确“路径”、“选择列表”、“结束条件”
3. 掌握笛卡尔积：这是组合生成的基础
4. 刷相关题：巩固回溯在不同场景的应用
5. 思考扩展：如支持更多字符、按需生成等

结语：电话号码的字母组合虽是一道“简单”的回溯题，却完美展示了如何将现实问题转化为算法模型。掌握它，不仅是为了解决这一道题，更是为了建立起解决更复杂组合问题的能力。希望本文能助你透彻理解回溯算法，在面试与实战中游刃有余！