leetcode17.电话号码的字母组合：字符串映射与回溯的巧妙联动

一、题目深度解析与字符映射逻辑

题目描述

给定一个仅包含数字 2-9 的字符串 digits，返回所有它能表示的字母组合。数字与字母的映射关系如下（与电话按键相同）：

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

例如，输入 digits = "23"，应返回 ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。题目要求：

• 输出的字母组合需包含所有可能情况
• 每个数字对应字母的不同组合都要考虑
• 结果顺序不做要求

核心难点剖析

本题的关键在于如何根据数字字符串的每个字符，找到对应的字母集合，并通过回溯算法生成所有可能的组合。其中，数字与字母的映射关系需要通过数据结构记录，而回溯过程中的状态管理则是确保组合完整性的核心。

二、递归回溯解法的核心实现与逻辑框架

class Solution {// 数字到字母的映射数组，0和1无对应字母，用空字符串占位String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};List<String> res = new ArrayList<>();  // 存储所有结果组合StringBuilder sb = new StringBuilder();  // 记录当前组合public List<String> letterCombinations(String digits) {if (digits.length() == 0) {return res;  // 处理空字符串输入}backtracking(digits, 0);  // 从第一个数字开始回溯return res;  // 返回所有组合}public void backtracking(String digits, int num) {if (num == digits.length()) {res.add(sb.toString());  // 保存当前组合return;}// 获取当前数字对应的字母字符串String str = numString[digits.charAt(num) - '0'];for (int i = 0; i < str.length(); i++) {sb.append(str.charAt(i));  // 选择当前字母backtracking(digits, num + 1);  // 递归处理下一个数字sb.deleteCharAt(sb.length() - 1);  // 回溯：撤销当前选择}}
}

核心设计解析

1. 字符映射数组：
   • numString数组建立数字与字母的映射关系，通过numString[digits.charAt(num) - '0']可快速获取对应字母集合。其中，- '0'的操作将字符类型的数字转换为数组索引所需的整数类型。
2. 结果与状态变量：
   • res：使用ArrayList存储所有符合要求的字母组合。
   • sb：StringBuilder用于高效构建当前组合，避免频繁字符串拼接带来的性能损耗。
3. 递归终止条件：
   • if (num == digits.length())：当处理完数字字符串的所有字符时，将当前sb记录的组合加入res，并结束当前递归分支。
4. 回溯核心逻辑：
   • 遍历当前数字对应的字母字符串，每次选择一个字母加入sb。
   • 递归调用backtracking处理下一个数字。
   • 递归返回后，通过sb.deleteCharAt(sb.length() - 1)删除最后一个字母，回溯到上一状态，尝试其他可能的组合。

三、核心问题解析：字符串映射与回溯联动

1. 数字字符到字母集合的映射实现

numString数组是连接数字与字母的桥梁。以输入字符串"23"为例：

• 处理第一个数字'2'时，numString[2 - '0']获取到"abc"，即数字2对应的字母集合。
• 处理第二个数字'3'时，numString[3 - '0']获取到"def"。

这种映射方式通过数组下标直接定位，时间复杂度为O(1)，相比使用Map等数据结构更加简洁高效。

2. 回溯算法的具体执行逻辑

在backtracking方法中，回溯过程通过递归与状态回退实现：

• 选择阶段：

  sb.append(str.charAt(i));
  backtracking(digits, num + 1);
  

  每次从当前数字对应的字母集合中选择一个字母加入sb，并递归处理下一个数字，深入探索当前选择下的所有可能组合。
• 回退阶段：

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

  递归返回后，删除sb中最后一个字母，撤销当前选择，以便尝试该数字对应的其他字母，确保所有组合都能被枚举到。

3. 递归过程中的状态传递

在递归调用过程中，num参数记录当前处理的数字位置，sb则记录当前构建的组合状态。每一层递归都基于上一层的状态继续构建，确保组合的完整性和准确性。例如：

• 当处理数字字符串"23"时，第一层递归处理数字2，第二层递归处理数字3。在第二层递归中，sb已包含第一层递归选择的字母（如'a'），在此基础上继续添加数字3对应的字母（如'd'），最终形成组合"ad"。

四、递归流程深度模拟：以输入"23"为例

1. 初始调用：backtracking("23", 0)
   • num = 0，处理第一个数字'2'，str = "abc"。
2. 选择字母'a'：
   • sb.append('a')，此时sb = "a"。
   • 递归调用backtracking("23", 1)，处理第二个数字'3'，str = "def"。
   • 选择字母'd'，sb.append('d')，此时sb = "ad"，满足终止条件，将"ad"加入res。
   • 回溯：sb.deleteCharAt(sb.length() - 1)，sb变回"a"，继续选择字母'e'，形成"ae"并加入res，以此类推，完成数字3对应字母的所有组合。
3. 回到数字2的处理：
   • 撤销字母'a'的选择，sb.deleteCharAt(sb.length() - 1)，sb清空。
   • 选择字母'b'，重复上述递归过程，生成以'b'开头的所有组合（如"bd"、"be"、"bf"）。
4. 选择字母'c'：
   • 同样进行递归与回溯，生成以'c'开头的所有组合（如"cd"、"ce"、"cf"）。
5. 最终结果：
   res包含["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]，涵盖所有可能的字母组合。

五、算法复杂度分析

1. 时间复杂度

假设数字字符串digits的长度为n，每个数字平均对应m个字母（实际最多4个）。

• 对于每个数字，都需要遍历其对应的字母集合，因此时间复杂度为$O(m^n)$ 。因为每个数字位置都有m种选择，总共n个位置，属于指数级复杂度。

2. 空间复杂度

• 递归栈的深度最大为n，因此空间复杂度为$O(n)$ 。
• res存储所有结果组合，最坏情况下，组合数量为$m^n$，每个组合长度为n，因此res占用空间为$O(n\times m^n)$ 。整体空间复杂度主要由res决定，为$O(n\times m^n)$ 。

六、核心技术点总结：字母组合生成的关键要素

1. 字符映射设计：通过数组建立数字与字母的高效映射，简化查找过程。
2. 回溯状态管理：利用StringBuilder动态构建组合，并通过递归与回退操作确保枚举所有可能组合。
3. 递归终止条件：根据数字字符串的处理进度判断是否完成一个组合的构建，及时保存结果。

七、常见误区与优化建议

1. 字符转换错误

• 误区：遗漏- '0'操作，导致无法正确获取字母集合。

  String str = numString[digits.charAt(num)]; // 错误，未转换字符为数字
  

• 正确做法：使用numString[digits.charAt(num) - '0']将字符类型数字转换为数组索引。

2. 回溯状态未完全回退

• 误区：在递归返回后，未删除sb中的最后一个字母，导致后续组合错误。

  sb.append(str.charAt(i));
  backtracking(digits, num + 1);
  // 缺少 sb.deleteCharAt(sb.length() - 1);
  

• 正确做法：确保在每次递归返回后，通过sb.deleteCharAt(sb.length() - 1)撤销当前选择。

3. 优化建议：迭代实现

若担心递归深度过深导致栈溢出，可以考虑使用迭代方式，借助队列或栈模拟递归过程。例如，使用队列存储中间状态，每次从队列中取出一个状态，扩展下一个数字对应的字母组合并重新入队，直至处理完所有数字。这种方式可以将空间复杂度优化为$O(m^n)$ ，避免递归栈的潜在风险。

通过对本题递归回溯解法的详细剖析，我们深入理解了如何利用字符串映射和回溯算法，高效生成电话号码对应的字母组合。这种解题思路在处理组合枚举类问题时具有广泛的应用价值，能够帮助我们解决更多类似的算法问题。