017.电话号码的字母组合

作者：沉默王二 发布时间：2024-01-29T21:09:33.198+0800

---

鲁迅说过，“读书不觉已春深，一寸光阴一寸金”，这句话用在学习算法上也是非常合适的，每天都要坚持学习，不要等到面试的时候才临时抱佛脚，那样的话，你就输了。今天继续刷《二哥的 LeetCode 刷题笔记》，开心。

技术派阅读地址：https://paicoding.com/column/7/17

• 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

• 这道题可以说完全重写了，给出3道大家完全都能掌握的题解（排列组合和回溯）。

• 增加代码注释，这样大家更容易看懂并掌握题解；

• 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

• 增加手绘图，这样大家更容易理解解题思路；

• 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

• 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

• 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

• 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

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

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

难度

中等

示例

输入：digits = "23"

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

分析 1

这道题对于新手来说，可能第一时间会比较难消化，但耐着性子思考一下，思路就很清晰了。

比如说 2 对应的是 abc，3 对应的是 def，那么 23 对应的就是 ad、ae、af、bd、be、bf、cd、ce、cf。

也就是一个排列组合。

那我们的思路如下：

①、建立一个数字到字母的映射，比如 2 对应的是 abc，3 对应的是 def，我们用数组来就可以。

// 数字到字母的映射

0 和 1 属于占位符，没有对应的字母，因为输入的字符串只包含 2-9 的数字。

②、建立一个队列，我们用**LinkedList **来实现，初始时队列中只有一个空字符串。

LinkedList combinations = new LinkedList<>();

空字符串是为了方便后续的处理，否则下面这两个方法就没办法直接使用，要判空，很麻烦。

combinations.peek();

③、第一层 for 循环，遍历输入的字符串，比如说 23，遍历 2 和 3，排列组合嘛。

for (int i = 0; i }

④、while 循环负责将队列中的字符串取出，并且与上一步中组合过的字母进行组合，比如说输入是 234 的时候，2 与 “” 空字符串组合，结果为 a、b、c，3 与 2 对应的 a、b、c 组合，4 与 23 组合后的 "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf" 组合。依次类推。

while (combinations.peek().length() == i) {

	// ...}

peek() 方法用于获取队列的头部元素，但不会移除这个元素，remove() 方法用于获取队列的头部元素，并且移除这个元素，防止重复组合，用过了就删除。

⑤、第二层 for 循环，遍历当前数字对应的所有字母，比如说 2 对应的是 abc，3 对应的是 def。

for (char s : mapping[digit].toCharArray()) {

}

来看完整的题解代码：

class Solution {

        LinkedList<String> combinations = new LinkedList<>();        // 如果输入为空，直接返回空列表        if (digits == null || digits.length() == 0) {            return combinations;        }
        // 数字到字母的映射        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};        combinations.add(""); // 初始添加一个空字符串到队列中
        // 遍历每个数字        for (int i = 0; i < digits.length(); i++) {            int digit = Character.getNumericValue(digits.charAt(i)); // 将当前字符转换为数字            // 当队列中的字符串长度与当前处理的数字索引相同时，处理队列中的字符串            while (combinations.peek().length() == i) {                String t = combinations.remove(); // 从队列中取出一个字符串                // 遍历当前数字对应的所有字母                for (char s : mapping[digit].toCharArray()) {                    combinations.add(t + s); // 将取出的字符串与当前字母相结合，然后加入队列中                }            }        }        return combinations; // 返回包含所有组合的列表    }}

当输入 digits = "23" 时，我们来模拟一下整个题解过程：

#### **初始化**

- mapping: {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
- combinations: [""] (初始时只包含一个空字符串)

#### **迭代过程**

①、**处理数字 '2'**（对应 "abc"）

- 从 combinations 中取出 "" (队列现在为空)
- 将 "" 与 "abc" 中的每个字符结合
- 新的组合: ["a", "b", "c"] 加入到队列

③、**处理数字 '3'**（对应 "def"）

- 从 combinations 中取出 "a" (队列中还剩 "b", "c")
- 将 "a" 与 "def" 中的每个字符结合
- 新的组合: ["ad", "ae", "af"] 加入到队列
- 接下来取出 "b"，重复上述过程
- 新的组合: ["ad", "ae", "af", "bd", "be", "bf"]
- 最后取出 "c"，重复上述过程
- 最终组合: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

#### **最终结果**

- combinations: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
- 返回。

注意 int digit = Character.getNumericValue(digits.charAt(i)); 这一行代码，这里是将当前字符转换为数字，比如说 Character.getNumericValue('2') 的结果就是 2。我们在《**[二哥的 Java 进阶之路](https://javabetter.cn/basic-grammar/basic-data-type.html#_04%E3%80%81int-%E5%92%8C-char-%E7%B1%BB%E5%9E%8B%E4%BA%92%E8%BD%AC)**》里也讲过。

大家也可以通过 ACM 的方式 debug 一下整个题解的过程，就会有一个更清晰的认知。

class Main01701 {

        Solution01701 solution = new Solution01701();        List<String> ans = solution.letterCombinations("234");        System.out.println(ans);    }}
class Solution01701 {    public List<String> letterCombinations(String digits) {        LinkedList<String> combinations = new LinkedList<>();        // 如果输入为空，直接返回空列表        if (digits == null || digits.length() == 0) {            return combinations;        }
        // 数字到字母的映射        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};        combinations.add(""); // 初始添加一个空字符串到队列中
        // 遍历每个数字        for (int i = 0; i < digits.length(); i++) {            int digit = Character.getNumericValue(digits.charAt(i)); // 将当前字符转换为数字            // 当队列中的字符串长度与当前处理的数字索引相同时，处理队列中的字符串            while (combinations.peek().length() == i) {                String t = combinations.remove(); // 从队列中取出一个字符串                // 遍历当前数字对应的所有字母                for (char s : mapping[digit].toCharArray()) {                    combinations.add(t + s); // 将取出的字符串与当前字母相结合，然后加入队列中                }            }        }        return combinations; // 返回包含所有组合的列表    }}

整个题解的过程如下所示：

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_18.png)

来看一下题解效率：

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_19.png)

### **分析 2**

题解很容易懂，但效率似乎不太理想，需要进一步优化。

比较耗时的操作应该发生在**[字符串的连接](https://javabetter.cn/string/join.html)**操作上 t + s，尤其是当输入的字符串长度很长的时候，这个操作就会很耗时。

class Solution {

        if (digits == null || digits.isEmpty()) {            return new ArrayList<>();        }
        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};        LinkedList<StringBuilder> combinations = new LinkedList<>();        combinations.add(new StringBuilder());
        for (int i = 0; i < digits.length(); i++) {            int digit = Character.getNumericValue(digits.charAt(i));            while (combinations.peek().length() == i) {                StringBuilder prefix = combinations.remove();                for (char letter : mapping[digit].toCharArray()) {                    combinations.add(new StringBuilder(prefix).append(letter));                }            }        }
        List<String> result = new ArrayList<>();        for (StringBuilder sb : combinations) {            result.add(sb.toString());        }        return result;    }}

我们将 combinations 队列中的元素从 String 类型改为 StringBuilder 类型，这样就可以直接在队列中进行字符串的连接操作，而不需要每次都新建一个字符串。

combinations.add(newStringBuilder(prefix).append(letter));

效率竟然提升了不少：

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_20.png)

这是我没能想到的，因为 + 号操作符本身就是用 StringBuilder 实现的。不知道是不是 LeetCode 的时间复杂度计算有问题😂

### **分析 3**

好，上面的全排列，也就是最容易掌握的暴力算法，已经没有优化空间了，那我们这里就要引入一个之前没有提到过的算法——回溯算法。

**回溯算法其实是一种穷举的递归算法**，它不断地在每一层试错，如果发现不符合条件的情况，就回退到上一层，然后尝试其他的可能，直到找到符合条件的情况。

如果之前没有了解过回溯算法的话，我这里给大家推荐一个视频，相信你看完后会有所帮助：**[回溯算法核心套路详解](https://www.bilibili.com/video/BV1P5411N7Xc/)**

文档的话，可以看看这个**[回溯算法的帖子](https://www.hello-algo.com/chapter_backtracking/backtracking_algorithm/)**

这里我总结一些回溯算法的关键要素。

**①、尝试与回退**：之所以叫回溯算法，是因为在尝试过程中，如果发现不符合条件的情况，就回退到上一层，然后尝试其他的可能，直到找到符合条件的情况。

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_21.png)

电话号码的字母组合，其实也可以转换成一棵树，把 2 和 3 节点的所有路径穷举一遍，就是我们要找的答案。

**②、剪枝**：复杂的回溯通常包含一些约束条件，约束条件就是剪枝的依据，比如说，题目要求我们找出所有的字母组合，但不包含 b，那么我们就可以在遍历的时候，把 b 剪掉。

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_22.png)

**③、递归**：回溯算法是一种穷举的递归算法，那我们就可以来描述一个回溯算法的框架：

void backtrack(路径, 选择列表) {

		result.add(路径);		return;	}
	for (选择 : 选择列表) {		做选择;		backtrack(路径, 选择列表);		撤销选择;	}}

好，我们来看一下题解代码：

class Solution {

	String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};	// 存储结果	List<String> result = new ArrayList<>();
	public List<String> letterCombinations(String digits) {		if (digits == null || digits.isEmpty()) {			return result;		}		// 回溯		backtrack(digits, 0, new StringBuilder());		return result;	}
	/**	 * 回溯算法	 *	 * @param digits 输入的数字字符串	 * @param index  当前处理的数字索引	 * @param sb     当前的组合	 */	private void backtrack(String digits, int index, StringBuilder sb) {		// 如果当前处理的数字索引等于数字字符串的长度，说明已经处理完了，直接将当前的组合加入到结果中		if (index == digits.length()) {			result.add(sb.toString());			return;		}		// 获取当前数字字符		char digit = digits.charAt(index);		// 获取当前数字字符对应的字母		String letters = mapping[digit - '0'];		// 遍历当前数字字符对应的所有字母		for (char letter : letters.toCharArray()) {			sb.append(letter); // 将当前字母加入到组合中			backtrack(digits, index + 1, sb); // 处理下一个数字字符			sb.deleteCharAt(sb.length() - 1); // 回溯，将当前字母从组合中删除		}	}}

当输入是 "234" 时，我们来模拟一下整个题解过程：

①、**初始调用**：调用 letterCombinations("234")。因为输入不是空，所以开始执行回溯算法。

②、**第一层回溯**：

- 输入的第一个数字是 '2'，对应的字母是 "abc"。
- 遍历 "abc"，每个字母都会进入下一层回溯。

③、**第二层回溯**：

- 输入的第二个数字是 '3'，对应的字母是 "def"。
- 对于 "def" 中的每个字母，同样会进入下一层回溯。

④、**第三层回溯**：

- 假设第一层选择了 'a'，第二层选择了 'd'，那么现在的字符串是 "ad"。
- 输入的第三个数字是 '4'，对应的字母是 "ghi"。
- 遍历 "ghi"，每个字母都会加入到字符串中，并因为已经到达字符串长度，将生成的组合加入结果中，然后返回，比如说 "adg"、"adh"、"adi"。

⑤、**回溯过程**：

- 一旦第三层回溯完成，控制回到第二层，删除当前层加入的字母，尝试下一个字母。比如，从 "adg" 变为 "ad"，然后尝试 "adh"、"adi"。
- 类似地，第二层完成后，控制回到第一层，删除当前层加入的字母，尝试下一个字母。比如，从 "ad" 变为 "a"，然后尝试 "ae"、"af"。
- sb.deleteCharAt([sb.length](http://sb.length)() - 1); 这行代码就是回溯的关键，每次回溯都会将当前层加入的字母删除，然后尝试下一个字母。

⑥、**结束条件**：

- 这个过程会一直重复，直到所有的组合都被尝试过。
- 最后，当所有可能的字母组合都被添加到结果列表后，回溯算法结束。

举个具体的例子，当我们以 "234" 为输入时，首先尝试的组合会是 "adg"，然后是 "adh"，"adi"，之后回到第二层尝试 "ae" 开头的组合，如此类推，直到最后一个组合 "cfi" 被添加到结果中。

OK，来看一下题解效率：

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_23.png)

这次 beat 了 100% 的用户，搞定。

这里有一个需要注意的点，就是 digit - '0'，这里是将字符转换为数字，比如说 '2' - '0' 的结果就是 2。《**[二哥的 Java 进阶之路](https://javabetter.cn/basic-grammar/basic-data-type.html#_04%E3%80%81int-%E5%92%8C-char-%E7%B1%BB%E5%9E%8B%E4%BA%92%E8%BD%AC)**》我们也讲过。

### **总结**

本题我们讲了排列组合和回溯算法，都是非常朴素的题解方法，很多时候，考虑到答题的时间，我们都会选择这种暴力算法。

针对排列组合的题目，回溯算法的效率也非常的高，也很容易理解和掌握。利用递归取代了循环，代码也更加简洁。

这里题涉及到的 Java 基础知识有：

- **[LinkedList 的 peek 和 remove](https://javabetter.cn/collection/linkedlist.html)**
- **[字符和数字之间的转换](https://javabetter.cn/basic-grammar/basic-data-type.html#_04%E3%80%81int-%E5%92%8C-char-%E7%B1%BB%E5%9E%8B%E4%BA%92%E8%BD%AC)**
- **[for 循环和 while 循环](https://javabetter.cn/basic-grammar/flow-control.html)**
- **[StringBuilder 的使用](https://javabetter.cn/string/builder-buffer.html)**

力扣链接：**[https://leetcode.cn/problems/letter-combinations-of-a-phone-number/](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/)**

### **一步一个脚印**

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**[二哥编程星球](https://javabetter.cn/zhishixingqiu/)**的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_24.png)

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

        
        

鲁迅说过，****“读书不觉已春深，一寸光阴一寸金”****，这句话用在学习算法上也是非常合适的，每天都要坚持学习，不要等到面试的时候才临时抱佛脚，那样的话，你就输了。今天继续刷《二哥的 LeetCode 刷题笔记》，开心。

技术派阅读地址：[https://paicoding.com/column/7/17](https://paicoding.com/column/7/17)

- 语雀专栏地址+密码可通过星球置顶帖查看：[https://t.zsxq.com/15rEo9Pdu](https://t.zsxq.com/15rEo9Pdu)
- 这道题可以说完全重写了，给出3道大家完全都能掌握的题解（排列组合和回溯）。

- 增加代码注释，这样大家更容易看懂并掌握题解；
- 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
- 增加手绘图，这样大家更容易理解解题思路；
- 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
- 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
- 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
- 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

### **题意**

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

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

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_17.png)

### **难度**

中等

### **示例**

输入：digits = "23"

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

### **分析 1**

这道题对于新手来说，可能第一时间会比较难消化，但耐着性子思考一下，思路就很清晰了。

比如说 2 对应的是 abc，3 对应的是 def，那么 23 对应的就是 ad、ae、af、bd、be、bf、cd、ce、cf。

也就是一个排列组合。

那我们的思路如下：

①、建立一个数字到字母的映射，比如 2 对应的是 abc，3 对应的是 def，我们用数组来就可以。

// 数字到字母的映射

0 和 1 属于占位符，没有对应的字母，因为输入的字符串只包含 2-9 的数字。

②、建立一个队列，我们用**[LinkedList](https://javabetter.cn/collection/linkedlist.html)**来实现，初始时队列中只有一个空字符串。

LinkedList combinations = new LinkedList<>();

空字符串是为了方便后续的处理，否则下面这两个方法就没办法直接使用，要判空，很麻烦。

combinations.peek();

③、第一层 for 循环，遍历输入的字符串，比如说 23，遍历 2 和 3，排列组合嘛。

for (int i = 0; i }

④、while 循环负责将队列中的字符串取出，并且与上一步中组合过的字母进行组合，比如说输入是 234 的时候，2 与 “” 空字符串组合，结果为 a、b、c，3 与 2 对应的 a、b、c 组合，4 与 23 组合后的 "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf" 组合。依次类推。

while (combinations.peek().length() == i) {

// ...}

peek() 方法用于获取队列的头部元素，但不会移除这个元素，remove() 方法用于获取队列的头部元素，并且移除这个元素，防止重复组合，用过了就删除。

⑤、第二层 for 循环，遍历当前数字对应的所有字母，比如说 2 对应的是 abc，3 对应的是 def。

for (char s : mapping[digit].toCharArray()) {

}

来看完整的题解代码：

class Solution {

    LinkedList<String> combinations = new LinkedList<>();        // 如果输入为空，直接返回空列表        if (digits == null || digits.length() == 0) {            return combinations;        }
    // 数字到字母的映射        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};        combinations.add(""); // 初始添加一个空字符串到队列中
    // 遍历每个数字        for (int i = 0; i < digits.length(); i++) {            int digit = Character.getNumericValue(digits.charAt(i)); // 将当前字符转换为数字            // 当队列中的字符串长度与当前处理的数字索引相同时，处理队列中的字符串            while (combinations.peek().length() == i) {                String t = combinations.remove(); // 从队列中取出一个字符串                // 遍历当前数字对应的所有字母                for (char s : mapping[digit].toCharArray()) {                    combinations.add(t + s); // 将取出的字符串与当前字母相结合，然后加入队列中                }            }        }        return combinations; // 返回包含所有组合的列表    }}

当输入 digits = "23" 时，我们来模拟一下整个题解过程：

初始化

• mapping: {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
• combinations: [""] (初始时只包含一个空字符串)

迭代过程

①、处理数字 '2'（对应 "abc"）

• 从 combinations 中取出 "" (队列现在为空)
• 将 "" 与 "abc" 中的每个字符结合
• 新的组合: ["a", "b", "c"] 加入到队列

③、处理数字 '3'（对应 "def"）

• 从 combinations 中取出 "a" (队列中还剩 "b", "c")
• 将 "a" 与 "def" 中的每个字符结合
• 新的组合: ["ad", "ae", "af"] 加入到队列
• 接下来取出 "b"，重复上述过程
• 新的组合: ["ad", "ae", "af", "bd", "be", "bf"]
• 最后取出 "c"，重复上述过程
• 最终组合: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

最终结果

• combinations: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
• 返回。

注意 int digit = Character.getNumericValue(digits.charAt(i)); 这一行代码，这里是将当前字符转换为数字，比如说 Character.getNumericValue('2') 的结果就是 2。我们在《二哥的 Java 进阶之路 》里也讲过。

大家也可以通过 ACM 的方式 debug 一下整个题解的过程，就会有一个更清晰的认知。

class Main01701 {

    Solution01701 solution = new Solution01701();        List<String> ans = solution.letterCombinations("234");        System.out.println(ans);    }}

class Solution01701 { public List letterCombinations(String digits) { LinkedList combinations = new LinkedList<>(); // 如果输入为空，直接返回空列表 if (digits == null || digits.length() == 0) { return combinations; } // 数字到字母的映射 String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; combinations.add(""); // 初始添加一个空字符串到队列中 // 遍历每个数字 for (int i = 0; i < digits.length(); i++) { int digit = Character.getNumericValue(digits.charAt(i)); // 将当前字符转换为数字 // 当队列中的字符串长度与当前处理的数字索引相同时，处理队列中的字符串 while (combinations.peek().length() == i) { String t = combinations.remove(); // 从队列中取出一个字符串 // 遍历当前数字对应的所有字母 for (char s : mapping[digit].toCharArray()) { combinations.add(t + s); // 将取出的字符串与当前字母相结合，然后加入队列中 } } } return combinations; // 返回包含所有组合的列表 }}

整个题解的过程如下所示：

来看一下题解效率：

分析 2

题解很容易懂，但效率似乎不太理想，需要进一步优化。

比较耗时的操作应该发生在**字符串的连接 **操作上 t + s，尤其是当输入的字符串长度很长的时候，这个操作就会很耗时。

class Solution {

    if (digits == null || digits.isEmpty()) {            return new ArrayList<>();        }
    String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};        LinkedList<StringBuilder> combinations = new LinkedList<>();        combinations.add(new StringBuilder());
    for (int i = 0; i < digits.length(); i++) {            int digit = Character.getNumericValue(digits.charAt(i));            while (combinations.peek().length() == i) {                StringBuilder prefix = combinations.remove();                for (char letter : mapping[digit].toCharArray()) {                    combinations.add(new StringBuilder(prefix).append(letter));                }            }        }
    List<String> result = new ArrayList<>();        for (StringBuilder sb : combinations) {            result.add(sb.toString());        }        return result;    }}

我们将 combinations 队列中的元素从 String 类型改为 StringBuilder 类型，这样就可以直接在队列中进行字符串的连接操作，而不需要每次都新建一个字符串。

combinations.add(newStringBuilder(prefix).append(letter));

效率竟然提升了不少：

这是我没能想到的，因为 + 号操作符本身就是用 StringBuilder 实现的。不知道是不是 LeetCode 的时间复杂度计算有问题😂

分析 3

好，上面的全排列，也就是最容易掌握的暴力算法，已经没有优化空间了，那我们这里就要引入一个之前没有提到过的算法——回溯算法。

回溯算法其实是一种穷举的递归算法，它不断地在每一层试错，如果发现不符合条件的情况，就回退到上一层，然后尝试其他的可能，直到找到符合条件的情况。

如果之前没有了解过回溯算法的话，我这里给大家推荐一个视频，相信你看完后会有所帮助：回溯算法核心套路详解

文档的话，可以看看这个**回溯算法的帖子 **

这里我总结一些回溯算法的关键要素。

①、尝试与回退：之所以叫回溯算法，是因为在尝试过程中，如果发现不符合条件的情况，就回退到上一层，然后尝试其他的可能，直到找到符合条件的情况。

电话号码的字母组合，其实也可以转换成一棵树，把 2 和 3 节点的所有路径穷举一遍，就是我们要找的答案。

②、剪枝：复杂的回溯通常包含一些约束条件，约束条件就是剪枝的依据，比如说，题目要求我们找出所有的字母组合，但不包含 b，那么我们就可以在遍历的时候，把 b 剪掉。

③、递归：回溯算法是一种穷举的递归算法，那我们就可以来描述一个回溯算法的框架：

void backtrack(路径, 选择列表) {

	result.add(路径);		return;	}
for (选择 : 选择列表) {		做选择;		backtrack(路径, 选择列表);		撤销选择;	}}

好，我们来看一下题解代码：

class Solution {

String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};	// 存储结果	List<String> result = new ArrayList<>();
public List<String> letterCombinations(String digits) {		if (digits == null || digits.isEmpty()) {			return result;		}		// 回溯		backtrack(digits, 0, new StringBuilder());		return result;	}
/**	 * 回溯算法	 *	 * @param digits 输入的数字字符串	 * @param index  当前处理的数字索引	 * @param sb     当前的组合	 */	private void backtrack(String digits, int index, StringBuilder sb) {		// 如果当前处理的数字索引等于数字字符串的长度，说明已经处理完了，直接将当前的组合加入到结果中		if (index == digits.length()) {			result.add(sb.toString());			return;		}		// 获取当前数字字符		char digit = digits.charAt(index);		// 获取当前数字字符对应的字母		String letters = mapping[digit - '0'];		// 遍历当前数字字符对应的所有字母		for (char letter : letters.toCharArray()) {			sb.append(letter); // 将当前字母加入到组合中			backtrack(digits, index + 1, sb); // 处理下一个数字字符			sb.deleteCharAt(sb.length() - 1); // 回溯，将当前字母从组合中删除		}	}}

当输入是 "234" 时，我们来模拟一下整个题解过程：

①、初始调用：调用 letterCombinations("234")。因为输入不是空，所以开始执行回溯算法。

②、第一层回溯：

• 输入的第一个数字是 '2'，对应的字母是 "abc"。
• 遍历 "abc"，每个字母都会进入下一层回溯。

③、第二层回溯：

• 输入的第二个数字是 '3'，对应的字母是 "def"。
• 对于 "def" 中的每个字母，同样会进入下一层回溯。

④、第三层回溯：

• 假设第一层选择了 'a'，第二层选择了 'd'，那么现在的字符串是 "ad"。
• 输入的第三个数字是 '4'，对应的字母是 "ghi"。
• 遍历 "ghi"，每个字母都会加入到字符串中，并因为已经到达字符串长度，将生成的组合加入结果中，然后返回，比如说 "adg"、"adh"、"adi"。

⑤、回溯过程：

• 一旦第三层回溯完成，控制回到第二层，删除当前层加入的字母，尝试下一个字母。比如，从 "adg" 变为 "ad"，然后尝试 "adh"、"adi"。
• 类似地，第二层完成后，控制回到第一层，删除当前层加入的字母，尝试下一个字母。比如，从 "ad" 变为 "a"，然后尝试 "ae"、"af"。
• sb.deleteCharAt(sb.length () - 1); 这行代码就是回溯的关键，每次回溯都会将当前层加入的字母删除，然后尝试下一个字母。

⑥、结束条件：

• 这个过程会一直重复，直到所有的组合都被尝试过。
• 最后，当所有可能的字母组合都被添加到结果列表后，回溯算法结束。

举个具体的例子，当我们以 "234" 为输入时，首先尝试的组合会是 "adg"，然后是 "adh"，"adi"，之后回到第二层尝试 "ae" 开头的组合，如此类推，直到最后一个组合 "cfi" 被添加到结果中。

OK，来看一下题解效率：

这次 beat 了 100% 的用户，搞定。

这里有一个需要注意的点，就是 digit - '0'，这里是将字符转换为数字，比如说 '2' - '0' 的结果就是 2。《二哥的 Java 进阶之路 》我们也讲过。

总结

本题我们讲了排列组合和回溯算法，都是非常朴素的题解方法，很多时候，考虑到答题的时间，我们都会选择这种暴力算法。

针对排列组合的题目，回溯算法的效率也非常的高，也很容易理解和掌握。利用递归取代了循环，代码也更加简洁。

这里题涉及到的 Java 基础知识有：

• LinkedList 的 peek 和 remove
• 字符和数字之间的转换
• for 循环和 while 循环
• StringBuilder 的使用

力扣链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

鲁迅说过，“读书不觉已春深，一寸光阴一寸金”，这句话用在学习算法上也是非常合适的，每天都要坚持学习，不要等到面试的时候才临时抱佛脚，那样的话，你就输了。今天继续刷《二哥的 LeetCode 刷题笔记》，开心。

技术派阅读地址：https://paicoding.com/column/7/17

• 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

• 这道题可以说完全重写了，给出3道大家完全都能掌握的题解（排列组合和回溯）。

• 增加代码注释，这样大家更容易看懂并掌握题解；

• 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

• 增加手绘图，这样大家更容易理解解题思路；

• 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

• 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

• 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

• 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

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

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

难度

中等

示例

输入：digits = "23"

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

分析 1

这道题对于新手来说，可能第一时间会比较难消化，但耐着性子思考一下，思路就很清晰了。

比如说 2 对应的是 abc，3 对应的是 def，那么 23 对应的就是 ad、ae、af、bd、be、bf、cd、ce、cf。

也就是一个排列组合。

那我们的思路如下：

①、建立一个数字到字母的映射，比如 2 对应的是 abc，3 对应的是 def，我们用数组来就可以。

// 数字到字母的映射

0 和 1 属于占位符，没有对应的字母，因为输入的字符串只包含 2-9 的数字。

②、建立一个队列，我们用**LinkedList **来实现，初始时队列中只有一个空字符串。

LinkedList combinations = new LinkedList<>();

空字符串是为了方便后续的处理，否则下面这两个方法就没办法直接使用，要判空，很麻烦。

combinations.peek();

③、第一层 for 循环，遍历输入的字符串，比如说 23，遍历 2 和 3，排列组合嘛。

for (int i = 0; i }

④、while 循环负责将队列中的字符串取出，并且与上一步中组合过的字母进行组合，比如说输入是 234 的时候，2 与 “” 空字符串组合，结果为 a、b、c，3 与 2 对应的 a、b、c 组合，4 与 23 组合后的 "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf" 组合。依次类推。

while (combinations.peek().length() == i) {

	// ...}

peek() 方法用于获取队列的头部元素，但不会移除这个元素，remove() 方法用于获取队列的头部元素，并且移除这个元素，防止重复组合，用过了就删除。

⑤、第二层 for 循环，遍历当前数字对应的所有字母，比如说 2 对应的是 abc，3 对应的是 def。

for (char s : mapping[digit].toCharArray()) {

}

来看完整的题解代码：

class Solution {

        LinkedList<String> combinations = new LinkedList<>();        // 如果输入为空，直接返回空列表        if (digits == null || digits.length() == 0) {            return combinations;        }
        // 数字到字母的映射        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};        combinations.add(""); // 初始添加一个空字符串到队列中
        // 遍历每个数字        for (int i = 0; i < digits.length(); i++) {            int digit = Character.getNumericValue(digits.charAt(i)); // 将当前字符转换为数字            // 当队列中的字符串长度与当前处理的数字索引相同时，处理队列中的字符串            while (combinations.peek().length() == i) {                String t = combinations.remove(); // 从队列中取出一个字符串                // 遍历当前数字对应的所有字母                for (char s : mapping[digit].toCharArray()) {                    combinations.add(t + s); // 将取出的字符串与当前字母相结合，然后加入队列中                }            }        }        return combinations; // 返回包含所有组合的列表    }}

当输入 digits = "23" 时，我们来模拟一下整个题解过程：

#### **初始化**

- mapping: {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
- combinations: [""] (初始时只包含一个空字符串)

#### **迭代过程**

①、**处理数字 '2'**（对应 "abc"）

- 从 combinations 中取出 "" (队列现在为空)
- 将 "" 与 "abc" 中的每个字符结合
- 新的组合: ["a", "b", "c"] 加入到队列

③、**处理数字 '3'**（对应 "def"）

- 从 combinations 中取出 "a" (队列中还剩 "b", "c")
- 将 "a" 与 "def" 中的每个字符结合
- 新的组合: ["ad", "ae", "af"] 加入到队列
- 接下来取出 "b"，重复上述过程
- 新的组合: ["ad", "ae", "af", "bd", "be", "bf"]
- 最后取出 "c"，重复上述过程
- 最终组合: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

#### **最终结果**

- combinations: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
- 返回。

注意 int digit = Character.getNumericValue(digits.charAt(i)); 这一行代码，这里是将当前字符转换为数字，比如说 Character.getNumericValue('2') 的结果就是 2。我们在《**[二哥的 Java 进阶之路](https://javabetter.cn/basic-grammar/basic-data-type.html#_04%E3%80%81int-%E5%92%8C-char-%E7%B1%BB%E5%9E%8B%E4%BA%92%E8%BD%AC)**》里也讲过。

大家也可以通过 ACM 的方式 debug 一下整个题解的过程，就会有一个更清晰的认知。

class Main01701 {

        Solution01701 solution = new Solution01701();        List<String> ans = solution.letterCombinations("234");        System.out.println(ans);    }}
class Solution01701 {    public List<String> letterCombinations(String digits) {        LinkedList<String> combinations = new LinkedList<>();        // 如果输入为空，直接返回空列表        if (digits == null || digits.length() == 0) {            return combinations;        }
        // 数字到字母的映射        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};        combinations.add(""); // 初始添加一个空字符串到队列中
        // 遍历每个数字        for (int i = 0; i < digits.length(); i++) {            int digit = Character.getNumericValue(digits.charAt(i)); // 将当前字符转换为数字            // 当队列中的字符串长度与当前处理的数字索引相同时，处理队列中的字符串            while (combinations.peek().length() == i) {                String t = combinations.remove(); // 从队列中取出一个字符串                // 遍历当前数字对应的所有字母                for (char s : mapping[digit].toCharArray()) {                    combinations.add(t + s); // 将取出的字符串与当前字母相结合，然后加入队列中                }            }        }        return combinations; // 返回包含所有组合的列表    }}

整个题解的过程如下所示：

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_18.png)

来看一下题解效率：

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_19.png)

### **分析 2**

题解很容易懂，但效率似乎不太理想，需要进一步优化。

比较耗时的操作应该发生在**[字符串的连接](https://javabetter.cn/string/join.html)**操作上 t + s，尤其是当输入的字符串长度很长的时候，这个操作就会很耗时。

class Solution {

        if (digits == null || digits.isEmpty()) {            return new ArrayList<>();        }
        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};        LinkedList<StringBuilder> combinations = new LinkedList<>();        combinations.add(new StringBuilder());
        for (int i = 0; i < digits.length(); i++) {            int digit = Character.getNumericValue(digits.charAt(i));            while (combinations.peek().length() == i) {                StringBuilder prefix = combinations.remove();                for (char letter : mapping[digit].toCharArray()) {                    combinations.add(new StringBuilder(prefix).append(letter));                }            }        }
        List<String> result = new ArrayList<>();        for (StringBuilder sb : combinations) {            result.add(sb.toString());        }        return result;    }}

我们将 combinations 队列中的元素从 String 类型改为 StringBuilder 类型，这样就可以直接在队列中进行字符串的连接操作，而不需要每次都新建一个字符串。

combinations.add(newStringBuilder(prefix).append(letter));

效率竟然提升了不少：

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_20.png)

这是我没能想到的，因为 + 号操作符本身就是用 StringBuilder 实现的。不知道是不是 LeetCode 的时间复杂度计算有问题😂

### **分析 3**

好，上面的全排列，也就是最容易掌握的暴力算法，已经没有优化空间了，那我们这里就要引入一个之前没有提到过的算法——回溯算法。

**回溯算法其实是一种穷举的递归算法**，它不断地在每一层试错，如果发现不符合条件的情况，就回退到上一层，然后尝试其他的可能，直到找到符合条件的情况。

如果之前没有了解过回溯算法的话，我这里给大家推荐一个视频，相信你看完后会有所帮助：**[回溯算法核心套路详解](https://www.bilibili.com/video/BV1P5411N7Xc/)**

文档的话，可以看看这个**[回溯算法的帖子](https://www.hello-algo.com/chapter_backtracking/backtracking_algorithm/)**

这里我总结一些回溯算法的关键要素。

**①、尝试与回退**：之所以叫回溯算法，是因为在尝试过程中，如果发现不符合条件的情况，就回退到上一层，然后尝试其他的可能，直到找到符合条件的情况。

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_21.png)

电话号码的字母组合，其实也可以转换成一棵树，把 2 和 3 节点的所有路径穷举一遍，就是我们要找的答案。

**②、剪枝**：复杂的回溯通常包含一些约束条件，约束条件就是剪枝的依据，比如说，题目要求我们找出所有的字母组合，但不包含 b，那么我们就可以在遍历的时候，把 b 剪掉。

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_22.png)

**③、递归**：回溯算法是一种穷举的递归算法，那我们就可以来描述一个回溯算法的框架：

void backtrack(路径, 选择列表) {

		result.add(路径);		return;	}
	for (选择 : 选择列表) {		做选择;		backtrack(路径, 选择列表);		撤销选择;	}}

好，我们来看一下题解代码：

class Solution {

	String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};	// 存储结果	List<String> result = new ArrayList<>();
	public List<String> letterCombinations(String digits) {		if (digits == null || digits.isEmpty()) {			return result;		}		// 回溯		backtrack(digits, 0, new StringBuilder());		return result;	}
	/**	 * 回溯算法	 *	 * @param digits 输入的数字字符串	 * @param index  当前处理的数字索引	 * @param sb     当前的组合	 */	private void backtrack(String digits, int index, StringBuilder sb) {		// 如果当前处理的数字索引等于数字字符串的长度，说明已经处理完了，直接将当前的组合加入到结果中		if (index == digits.length()) {			result.add(sb.toString());			return;		}		// 获取当前数字字符		char digit = digits.charAt(index);		// 获取当前数字字符对应的字母		String letters = mapping[digit - '0'];		// 遍历当前数字字符对应的所有字母		for (char letter : letters.toCharArray()) {			sb.append(letter); // 将当前字母加入到组合中			backtrack(digits, index + 1, sb); // 处理下一个数字字符			sb.deleteCharAt(sb.length() - 1); // 回溯，将当前字母从组合中删除		}	}}

当输入是 "234" 时，我们来模拟一下整个题解过程：

①、**初始调用**：调用 letterCombinations("234")。因为输入不是空，所以开始执行回溯算法。

②、**第一层回溯**：

- 输入的第一个数字是 '2'，对应的字母是 "abc"。
- 遍历 "abc"，每个字母都会进入下一层回溯。

③、**第二层回溯**：

- 输入的第二个数字是 '3'，对应的字母是 "def"。
- 对于 "def" 中的每个字母，同样会进入下一层回溯。

④、**第三层回溯**：

- 假设第一层选择了 'a'，第二层选择了 'd'，那么现在的字符串是 "ad"。
- 输入的第三个数字是 '4'，对应的字母是 "ghi"。
- 遍历 "ghi"，每个字母都会加入到字符串中，并因为已经到达字符串长度，将生成的组合加入结果中，然后返回，比如说 "adg"、"adh"、"adi"。

⑤、**回溯过程**：

- 一旦第三层回溯完成，控制回到第二层，删除当前层加入的字母，尝试下一个字母。比如，从 "adg" 变为 "ad"，然后尝试 "adh"、"adi"。
- 类似地，第二层完成后，控制回到第一层，删除当前层加入的字母，尝试下一个字母。比如，从 "ad" 变为 "a"，然后尝试 "ae"、"af"。
- sb.deleteCharAt([sb.length](http://sb.length)() - 1); 这行代码就是回溯的关键，每次回溯都会将当前层加入的字母删除，然后尝试下一个字母。

⑥、**结束条件**：

- 这个过程会一直重复，直到所有的组合都被尝试过。
- 最后，当所有可能的字母组合都被添加到结果列表后，回溯算法结束。

举个具体的例子，当我们以 "234" 为输入时，首先尝试的组合会是 "adg"，然后是 "adh"，"adi"，之后回到第二层尝试 "ae" 开头的组合，如此类推，直到最后一个组合 "cfi" 被添加到结果中。

OK，来看一下题解效率：

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_23.png)

这次 beat 了 100% 的用户，搞定。

这里有一个需要注意的点，就是 digit - '0'，这里是将字符转换为数字，比如说 '2' - '0' 的结果就是 2。《**[二哥的 Java 进阶之路](https://javabetter.cn/basic-grammar/basic-data-type.html#_04%E3%80%81int-%E5%92%8C-char-%E7%B1%BB%E5%9E%8B%E4%BA%92%E8%BD%AC)**》我们也讲过。

### **总结**

本题我们讲了排列组合和回溯算法，都是非常朴素的题解方法，很多时候，考虑到答题的时间，我们都会选择这种暴力算法。

针对排列组合的题目，回溯算法的效率也非常的高，也很容易理解和掌握。利用递归取代了循环，代码也更加简洁。

这里题涉及到的 Java 基础知识有：

- **[LinkedList 的 peek 和 remove](https://javabetter.cn/collection/linkedlist.html)**
- **[字符和数字之间的转换](https://javabetter.cn/basic-grammar/basic-data-type.html#_04%E3%80%81int-%E5%92%8C-char-%E7%B1%BB%E5%9E%8B%E4%BA%92%E8%BD%AC)**
- **[for 循环和 while 循环](https://javabetter.cn/basic-grammar/flow-control.html)**
- **[StringBuilder 的使用](https://javabetter.cn/string/builder-buffer.html)**

力扣链接：**[https://leetcode.cn/problems/letter-combinations-of-a-phone-number/](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/)**

### **一步一个脚印**

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**[二哥编程星球](https://javabetter.cn/zhishixingqiu/)**的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_24.png)

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

        
                
                
                知识星球
                
        
        
            
            扫码加入星球
            查看更多优质内容
        
        https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412