LeetCode 17.电话号码的字母组合
题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。可以按任何顺序返回答案。
说明：
- 给定数字
2-9，每个数字对应的字母集合如下：2-> “abc”3-> “def”4-> “ghi”5-> “jkl”6-> “mno”7-> “pqrs”8-> “tuv”9-> “wxyz”
示例 1:
输入: "23"
输出: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
示例 2:
输入: ""
输出: []
Java 实现解法
import java.util.ArrayList;
import java.util.List;
public class Solution {
private static final String[] MAPPING = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return result;
}
backtrack(result, new StringBuilder(), digits, 0);
return result;
}
private void backtrack(List<String> result, StringBuilder current, String digits, int index) {
// 如果当前字符串长度等于 digits 长度，说明找到一个完整的组合
if (current.length() == digits.length()) {
result.add(current.toString());
return;
}
// 获取当前数字对应的字母集合
String letters = MAPPING[digits.charAt(index) - '0'];
for (char letter : letters.toCharArray()) {
current.append(letter); // 选择当前字母
backtrack(result, current, digits, index + 1); // 递归处理下一个数字
current.deleteCharAt(current.length() - 1); // 回溯，移除当前字母
}
}
}
解题思路
问题分析：
- 每个数字都对应着一定的字母集合，问题就是要找到所有这些字母组合的排列。
- 我们可以通过回溯来解决这个问题。每当处理一个数字时，我们从它对应的字母集合中选择一个字母，然后继续处理下一个数字。
- 当处理完所有数字时，就找到了一个完整的字母组合。
回溯法：
- 递归：我们从字符串的第一个数字开始，递归地选择每个数字的字母，直到所有数字都被处理完。每一次递归，我们将当前选中的字母加入到当前的组合中。
- 回溯：在递归回到上一层时，我们撤销上一步选择的字母，继续尝试其他可能的字母组合。
实现步骤：
- 定义一个映射数组
MAPPING，表示每个数字对应的字母集合。- 使用回溯法逐步构建所有的字母组合，直到遍历完所有数字。
- 如果字符串为空，直接返回一个空的结果列表。
复杂度分析
时间复杂度：
O(3^m×4^n)，其中m是输入中对应3个字母的数字个数（包括数字 2、3、4、5、6、8），n是输入中对应4个字母的数字个数（包括数字
7、9），m+n是输入数字的总个数。当输入包含m个对应3个字母的数字和n个对应4个字母的数字时，不同的字母组合一共有3^m×4^n种，需要遍历每一种字母组合。空间复杂度：：
O(m+n)，其中m是输入中对应3个字母的数字个数，n是输入中对应4个字母的数字个数，m+n是输入数字的总个数。递归调用层数最大为m+n`
输入示例
digits = "23"
回溯算法执行过程
初始化
映射数组：
MAPPING = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]对应：
2-> “abc”3-> “def”递归函数
backtrack(result, current, digits, index)：
result：存储所有生成的字母组合current：当前的字母组合（StringBuilder）digits：输入的数字字符串index：当前正在处理的数字的索引第一次递归（index = 0，处理数字 ‘2’）
- 当前
digits是 “23”，从index = 0开始。MAPPING[2] = "abc"，所以我们从'a','b','c'中选择。选择 ‘a’：
- 当前组合
current = "a"，递归到下一层，处理index = 1（即数字 ‘3’）。第二次递归（index = 1，处理数字 ‘3’）
- 当前数字是 ‘3’，
MAPPING[3] = "def"，所以我们从'd','e','f'中选择。选择 ‘d’：
当前组合
current = "ad"，递归到下一层，处理完所有数字（index = 2，超过了digits的长度）。添加
"ad"到结果集result = ["ad"]。选择 ‘e’：
当前组合
current = "ae"，递归到下一层，处理完所有数字。添加
"ae"到结果集result = ["ad", "ae"]。选择 ‘f’：
当前组合
current = "af"，递归到下一层，处理完所有数字。添加
"af"到结果集result = ["ad", "ae", "af"]。回溯到上一层，撤销选择 ‘f’，恢复
current = "a"。回到第一次递归，选择 ‘b’（index = 0）
- 当前组合
current = "b"，递归到下一层，处理数字 ‘3’（即index = 1）。第二次递归（index = 1，处理数字 ‘3’）
MAPPING[3] = "def"，从'd','e','f'中选择。选择 ‘d’：
当前组合
current = "bd"，递归到下一层，处理完所有数字。添加
"bd"到结果集result = ["ad", "ae", "af", "bd"]。选择 ‘e’：
当前组合
current = "be"，递归到下一层，处理完所有数字。添加
"be"到结果集result = ["ad", "ae", "af", "bd", "be"]。选择 ‘f’：
当前组合
current = "bf"，递归到下一层，处理完所有数字。添加
"bf"到结果集result = ["ad", "ae", "af", "bd", "be", "bf"]。回溯到上一层，撤销选择 ‘f’，恢复
current = "b"。回到第一次递归，选择 ‘c’（index = 0）
- 当前组合
current = "c"，递归到下一层，处理数字 ‘3’（即index = 1）。第二次递归（index = 1，处理数字 ‘3’）
MAPPING[3] = "def"，从'd','e','f'中选择。选择 ‘d’：
当前组合
current = "cd"，递归到下一层，处理完所有数字。添加
"cd"到结果集result = ["ad", "ae", "af", "bd", "be", "bf", "cd"]。选择 ‘e’：
当前组合
current = "ce"，递归到下一层，处理完所有数字。添加
"ce"到结果集result = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce"]。选择 ‘f’：
当前组合
current = "cf"，递归到下一层，处理完所有数字。添加
"cf"到结果集result = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。回溯到上一层，撤销选择 ‘f’，恢复
current = "c"。最终结果
回溯到最顶层，所有递归结束，最终生成的所有字母组合为：
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]总结
- 通过回溯算法，我们从每个数字开始，逐步选择它对应的字母，然后递归生成所有的字母组合。
- 每次递归结束后，我们通过回溯撤销之前的选择，继续探索其他可能的组合。
![[HCTF 2018]WarmUp 1--详细解析](https://i-blog.csdnimg.cn/direct/2bde6cc7672a4cd789748d08f81766a8.png)
