力扣热题100实战 | 第17期：电话号码的字母组合——回溯算法的经典启蒙

力扣热题100实战 | 第17期：电话号码的字母组合——回溯算法的经典启蒙

• • 前言
  • 一、题目：电话按键上的字母组合
  • • 关键点解读
  • 二、第一反应：多层循环嵌套（无法扩展）
  • • 代码实现
    • 这段代码的问题在哪？
  • 三、核心思路：回溯算法（多叉树遍历）
  • • 回溯思想
    • 回溯三要素
    • 算法步骤
  • 四、代码实现：回溯算法（面试标准答案）
  • • 代码解析
    • 复杂度分析
  • 五、另一种思路：BFS队列解法（拓展思维）
  • • BFS核心思想
    • BFS图解流程
    • BFS代码实现
    • DFS vs BFS
  • 六、细节剖析：面试官真正关心的问题
  • • Q1：为什么用 StringBuilder 而不用 String 拼接？
    • Q2：回溯时为什么要撤销选择？不撤销会怎样？
    • Q3：index 参数的作用是什么？
    • Q4：为什么映射表用数组而不用 HashMap？
    • Q5：时间复杂度中的 3^m × 4^n 是怎么来的？
  • 七、面试官追问进阶版
  • • 追问1：如果输入包含数字0和1，应该怎么处理？
    • 追问2：如何用迭代的方式（非递归）实现？
    • 追问3：如果要求输出的是字母组合的个数（而不列出具体组合），怎么算？
    • 追问4：如果数字可以重复，结果中会出现重复组合吗？
  • 八、实际开发：这道题到底有什么用？
  • • 场景1：输入法联想
    • 场景2：密码破解
    • 场景3：基因序列组合
    • 场景4：电话号码记忆
    • 场景5：自动化测试
  • 九、总结：从一道题到一类题
  • 附录：思考题

当一个问题需要“多选一”地构建所有可能结果时，回溯算法就是你最锋利的武器。而这道题，正是理解回溯思想的最佳起点。

前言

你好，我是@礼拜天没时间。

前十六期我们系统学习了哈希表、链表操作、滑动窗口、二分查找、动态规划、双指针、贪心算法等多种算法思想。这一期，我们来解一道全新的算法类型——回溯算法的入门经典：电话号码的字母组合（LeetCode 第17题）。

这道题在力扣上被标记为“中等”，但它的难度其实不高，真正有价值的是它作为回溯算法启蒙题的地位。回溯算法是解决排列、组合、子集等问题的通用框架，而这道题恰好展示了回溯最核心的思想——多叉树的遍历。

很多同学第一次接触回溯时，会被“递归”“撤销选择”这些概念绕晕。但当你把问题想象成在一棵树上从根走到叶子，一切就豁然开朗了。

今天，我希望能带你从决策树的视角，一次看懂回溯算法。

一、题目：电话按键上的字母组合

先看题目描述（LeetCode 第17题）：

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

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

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

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

关键点解读

二、第一反应：多层循环嵌套（无法扩展）

当我第一次看到这道题，我的第一反应是：用多层循环嵌套，根据输入长度决定循环层数。

代码实现

// 错误思路示例——只能处理固定长度
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits.length() == 2) {
String letters1 = getLetters(digits.charAt(0));
String letters2 = getLetters(digits.charAt(1));
for (char c1 : letters1.toCharArray()) {
for (char c2 : letters2.toCharArray()) {
result.add("" + c1 + c2);
}
}
} else if (digits.length() == 3) {
// 需要三层循环
// …
}
return result;
}

这段代码的问题在哪？

这正是回溯算法登场的地方——用递归代替多层循环，用回溯探索所有分支。

三、核心思路：回溯算法（多叉树遍历）

回溯思想

回溯算法的本质是多叉树的深度优先遍历（DFS）。我们可以把问题建模成一棵树：

• 树的根节点：空字符串
• 树的每一层：对应输入数字串中的一个位置
• 树的每个节点：代表当前已拼接的字母组合
• 树的叶子节点：代表一个完整的字母组合

以输入"23"为例，决策树如图所示：

root("")
/ | \\
2:a 2:b 2:c
/ | \\ / | \\ / | \\
3:d 3:e 3:f 3:d 3:e 3:f 3:d 3:e 3:f
/ | \\ / | \\ / | \\
ad ae af bd be bf cd ce cf

回溯三要素

回溯算法有三个核心要素：

算法步骤

四、代码实现：回溯算法（面试标准答案）

class Solution {
// 数字到字母的映射表
private String[] mapping = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};

public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return result;
}

backtrack(digits, 0, new StringBuilder(), result);
return result;
}

/**
* 回溯算法核心函数
* @param digits 输入的数字字符串
* @param index 当前处理到的数字位置
* @param path 当前已拼接的字母组合
* @param result 结果集
*/
private void backtrack(String digits, int index, StringBuilder path, List<String> result) {
// 结束条件：处理完所有数字
if (index == digits.length()) {
result.add(path.toString());
return;
}

// 获取当前数字对应的字母串
char digit = digits.charAt(index);
String letters = mapping[digit – '0'];

// 遍历每个字母
for (int i = 0; i < letters.length(); i++) {
char c = letters.charAt(i);

// 做选择：将当前字母加入路径
path.append(c);

// 递归处理下一个数字
backtrack(digits, index + 1, path, result);

// 撤销选择（回溯）：移除刚加入的字母
path.deleteCharAt(path.length() – 1);
}
}
}

代码解析

复杂度分析

• 时间复杂度：O(3^m × 4^n) —— 其中 m 是对应3个字母的数字个数（2,3,4,5,6,8），n 是对应4个字母的数字个数（7,9）。每个组合需要 O(len) 的时间构建。
• 空间复杂度：O(m + n) —— 递归栈的深度等于输入数字串的长度，不计结果集的空间。

五、另一种思路：BFS队列解法（拓展思维）

除了回溯（DFS），我们也可以用广度优先搜索（BFS）来解决这个问题。

BFS核心思想

用一个队列来存储中间结果，逐层扩展：

BFS图解流程

以输入"23"为例：

• 初始队列：[""]
• 处理数字2：队列弹出""，与"abc"拼接 → 队列变为 ["a","b","c"]
• 处理数字3：依次弹出"a"、“b”、“c”，分别与"def"拼接
  • 弹出"a" → 生成"ad",“ae”,"af"入队
  • 弹出"b" → 生成"bd",“be”,"bf"入队
  • 弹出"c" → 生成"cd",“ce”,"cf"入队
• 最终队列：["ad","ae","af","bd","be","bf","cd","ce","cf"]

BFS代码实现

class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return result;
}

String[] mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

// 使用LinkedList作为队列
Queue<String> queue = new LinkedList<>();
queue.offer("");

for (int i = 0; i < digits.length(); i++) {
char digit = digits.charAt(i);
String letters = mapping[digit – '0'];
int size = queue.size(); // 当前层的元素个数

// 处理当前层的所有元素
for (int j = 0; j < size; j++) {
String cur = queue.poll();
// 将当前字符串与每个字母拼接后入队
for (int k = 0; k < letters.length(); k++) {
queue.offer(cur + letters.charAt(k));
}
}
}

// 队列中剩余的就是所有组合
result.addAll(queue);
return result;
}
}

DFS vs BFS

建议：面试中优先掌握DFS回溯解法，BFS作为拓展思路了解即可。

六、细节剖析：面试官真正关心的问题

Q1：为什么用 StringBuilder 而不用 String 拼接？

答案：在回溯过程中，我们需要频繁地在末尾添加和删除字符。StringBuilder 的 append 和 deleteCharAt 都是 O(1) 操作。如果用 String 拼接，每次都会创建新对象，效率较低。

Q2：回溯时为什么要撤销选择？不撤销会怎样？

答案：如果不撤销选择，path 会一直累加，最终得到的是所有字母连在一起的字符串，而不是组合。例如"23"，如果第一次选了’a’，第二次选了’d’，得到"ad"；如果不撤销’d’，下一次就会在"ad"基础上继续加’e’，得到"ade"，这显然是错误的。

Q3：index 参数的作用是什么？

答案：index 有两个作用：

Q4：为什么映射表用数组而不用 HashMap？

答案：因为数字是连续且范围固定的（0-9），用数组可以通过 digit – '0' 直接索引，时间复杂度 O(1)，比 HashMap 更快。如果用 HashMap 也可以，但需要额外的哈希计算。

Q5：时间复杂度中的 3^m × 4^n 是怎么来的？

答案：数字2、3、4、5、6、8对应3个字母，数字7、9对应4个字母。设 m 为三字母数字的个数，n 为四字母数字的个数，则总组合数为 3^m × 4^n。例如输入"23"，m=2，n=0，总数为 3² = 9。

七、面试官追问进阶版

追问1：如果输入包含数字0和1，应该怎么处理？

思路：题目说0和1不对应任何字母，如果输入中包含它们，可以有两种处理方式：

• 直接忽略（跳过该数字）
• 视为空字符，不影响组合

// 修改后的代码
if (digit == '0' || digit == '1') {
// 跳过，递归下一个数字
backtrack(digits, index + 1, path, result);
return;
}

追问2：如何用迭代的方式（非递归）实现？

思路：可以用 BFS 队列解法，上面已经给出。也可以用累乘法：

public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits.length() == 0) return result;

result.add("");
String[] mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

for (int i = 0; i < digits.length(); i++) {
String letters = mapping[digits.charAt(i) – '0'];
List<String> newResult = new ArrayList<>();
for (String prefix : result) {
for (char c : letters.toCharArray()) {
newResult.add(prefix + c);
}
}
result = newResult;
}
return result;
}

追问3：如果要求输出的是字母组合的个数（而不列出具体组合），怎么算？

思路：直接套用乘法原理：对于每个数字，乘以其对应的字母个数。不需要回溯，一次遍历即可。

public int countCombinations(String digits) {
int[] counts = {0, 0, 3, 3, 3, 3, 3, 4, 3, 4}; // 0-9对应的字母个数
int result = 1;
for (char c : digits.toCharArray()) {
result *= counts[c – '0'];
}
return result;
}

追问4：如果数字可以重复，结果中会出现重复组合吗？

答案：会的。例如输入"22"，第一个2选’a’、第二个2选’b’得到"ab"，与第一个2选’b’、第二个2选’a’得到的"ba"是不同的组合，但题目要求的是所有组合，这些都应该保留。所以重复数字不影响结果，每个位置独立选择。

八、实际开发：这道题到底有什么用？

很多读者会问：“电话号码的字母组合，实际工作中哪用得到？”

其实它的思想无处不在：

场景1：输入法联想

在手机输入法中，当你按数字键时，系统需要预测你可能想输入的单词，这背后的算法就是根据数字到字母的映射生成候选词。

场景2：密码破解

在暴力破解密码时，有时需要枚举所有可能的字母组合。虽然实际密码不会这么简单，但思路是相通的。

场景3：基因序列组合

在生物信息学中，DNA序列由四种碱基组成，需要枚举所有可能的组合模式，这也可以用回溯算法。

场景4：电话号码记忆

有些公司会用字母代替电话号码（如1-800-FLOWERS），将字母转回数字时，就需要这种映射关系。

场景5：自动化测试

在测试输入框的边界值时，有时需要生成所有可能的字符组合，回溯算法可以派上用场。

九、总结：从一道题到一类题

回顾一下，我们从电话号码的字母组合学到了什么：

力扣热题100的第十七题，不是为了难住你，而是为了告诉你：当问题需要“尝试所有可能”时，回溯算法就是你最可靠的伙伴。掌握了回溯，你就掌握了排列、组合、子集等一系列问题的通解。

下一期预告：《四数之和》——双指针的再进阶

附录：思考题

看完这篇文章，你可以试着回答：

欢迎在评论区留下你的思考！