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

本文链接：https://blog.csdn.net/Musennn/article/details/148355846

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

题目描述

给定一个仅包含数字 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);  // 回溯：撤销当前选择
        }
    }
}

核心设计解析

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

初始调用：backtracking("23", 0)
- num = 0，处理第一个数字'2'，str = "abc"。
选择字母'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对应字母的所有组合。
回到数字2的处理：
- 撤销字母'a'的选择，sb.deleteCharAt(sb.length() - 1)，sb清空。
- 选择字母'b'，重复上述递归过程，生成以'b'开头的所有组合（如"bd"、"be"、"bf"）。
选择字母'c'：
- 同样进行递归与回溯，生成以'c'开头的所有组合（如"cd"、"ce"、"cf"）。
最终结果：
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占用空间为 $\times m^n)$ 。整体空间复杂度主要由res决定，为 $\times m^n)$ 。

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

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

七、常见误区与优化建议

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)$ ，避免递归栈的潜在风险。

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