17、电话号码的字母组合

题意

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

序 返回。

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

017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E

6%AF%8D%E7%BB%84%E5%90%88-20240128105403.png

难度

中等

示例

输入：digits = "23"

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

输入：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，我们用数组来

就可以。

// 数字到字母的映射

String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv",

"wxyz"};

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

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

LinkedList<String> combinations = new LinkedList<>();

combinations.add(""); // 初始添加一个空字符串到队列中

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

烦。

combinations.peek();

String t = combinations.remove();

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

for (int i = 0; i < digits.length(); 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) {

String t = combinations.remove();

// ...

}

peek() 方法用于获取队列的头部元素，但不会移除这个元素，remove() 方法用于获取队

列的头部元素，并且移除这个元素，防止重复组合，用过了就删除。

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

是 def。

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

// ...

}

来看完整的题解代码：

class Solution {

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; // 返回包含所有组合的列表

}

}

当输入 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 {

public static void main(String[] args) {

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; // 返回包含所有组合的列表

 }

}

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

017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E

6%AF%8D%E7%BB%84%E5%90%88-20240129155455.png

来看一下题解效率：

017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E

6%AF%8D%E7%BB%84%E5%90%88-20240129155521.png

分析 2

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

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

的时候，这个操作就会很耗时。

class Solution {

public List<String> letterCombinations(String digits) {

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(new StringBuilder(prefix).append(letter));

效率竟然提升了不少：

017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E

6%AF%8D%E7%BB%84%E5%90%88-20240129160754.png

?

这是我没能想到的，因为 + 号操作符本身就是用 StringBuilder 实现的。不知道是不是

LeetCode 的复度

杂度算

有计算 有 问题?

分析 3

好，上面的全排列，也就是最容易掌握的暴力算法，已经没有优化空间了，那我们这里就

要引入一个之前没有提到过的算法——回溯算法。

回溯算法其实是一种穷举的递归算法，它不断地在每一层试错，如果发现不符合条件的情

况，就回退到上一层，然后尝试其他的可能，直到找到符合条件的情况。

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

助：回溯算法核心套路详解

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

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

①、尝试与回退：之所以叫回溯算法，是因为在尝试过程中，如果发现不符合条件的情

况，就回退到上一层，然后尝试其他的可能，直到找到符合条件的情况。

017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E

6%AF%8D%E7%BB%84%E5%90%88-20240129201040.png

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

是我们要找的答案。

②、剪枝：复杂的回溯通常包含一些约束条件，约束条件就是剪枝的依据，比如说，题目

要求我们找出所有的字母组合，但不包含 b，那么我们就可以在遍历的时候，把 b 剪掉。

017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E

6%AF%8D%E7%BB%84%E5%90%88-20240129201529.png

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

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

if (满足结束条件) {

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，来看一下题解效率：

017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E

6%AF%8D%E7%BB%84%E5%90%88-20240129204953.png

这次 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/