内容介绍
给定一个仅包含数字
2-9
的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例 1:
输入:digits = "23" 输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]示例 2:
输入:digits = "" 输出:[]示例 3:
输入:digits = "2" 输出:["a","b","c"]提示:
0 <= digits.length <= 4
digits[i]
是范围['2', '9']
的一个数字。
完整代码
class Solution {public List<String> letterCombinations(String digits) {List<String> combinations = new ArrayList<String>();if (digits.length() == 0) {return combinations;}Map<Character, String> phoneMap = new HashMap<Character, String>() {{put('2', "abc");put('3', "def");put('4', "ghi");put('5', "jkl");put('6', "mno");put('7', "pqrs");put('8', "tuv");put('9', "wxyz");}};backtrack(combinations, phoneMap, digits, 0, new StringBuffer());return combinations;}public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {if (index == digits.length()) {combinations.add(combination.toString());} else {char digit = digits.charAt(index);String letters = phoneMap.get(digit);int lettersCount = letters.length();for (int i = 0; i < lettersCount; i++) {combination.append(letters.charAt(i));backtrack(combinations, phoneMap, digits, index + 1, combination);combination.deleteCharAt(index);}}}
}
思路详解
1. 初始化返回列表
List<String> combinations = new ArrayList<String>();
创建一个空列表combinations
,用于存储所有可能的字母组合。
2. 检查输入字符串是否为空
if (digits.length() == 0) {return combinations;
}
如果输入的数字字符串为空,则直接返回空列表。
3. 创建电话键盘映射
Map<Character, String> phoneMap = new HashMap<Character, String>() {{put('2', "abc");put('3', "def");put('4', "ghi");put('5', "jkl");put('6', "mno");put('7', "pqrs");put('8', "tuv");put('9', "wxyz");
}};
使用一个HashMap
来存储电话键盘上的数字到对应字母的映射。
4. 调用回溯函数
backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
调用backtrack
函数来填充combinations
列表,从索引0
开始,并使用一个StringBuffer
来构建当前的字母组合。
5. 定义回溯函数
public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
backtrack
是一个递归函数,用于生成所有可能的字母组合。
6. 回溯终止条件
if (index == digits.length()) {combinations.add(combination.toString());
}
当index
等于digits
的长度时,表示一个完整的组合已经构建完成,将其添加到combinations
列表中。
7. 构建组合
char digit = digits.charAt(index);
String letters = phoneMap.get(digit);
int lettersCount = letters.length();
for (int i = 0; i < lettersCount; i++) {combination.append(letters.charAt(i));backtrack(combinations, phoneMap, digits, index + 1, combination);combination.deleteCharAt(index);
}
对于当前数字digit
,获取其对应的字母字符串letters
,然后遍历这些字母:
- 将当前字母添加到
combination
中。 - 递归调用
backtrack
函数,将index
加1,表示向组合中添加下一个字母。 - 在递归返回后,移除
combination
中最后一个添加的字母,以便尝试下一个字母。
知识点精炼
总结
该代码通过回溯算法生成所有可能的字母组合。回溯是一种试探性的算法,它在每一步都尝试所有可能的选择,并在达到某个条件时回退到上一步,尝试其他选择。在电话键盘字母组合的问题中,回溯算法通过递归地构建每个数字对应的字母组合,最终生成所有可能的组合。
-
递归与回溯:
- 使用递归函数
backtrack
实现回溯算法,这是一种通过不断尝试所有可能的选择来找到所有解的算法。
- 使用递归函数
-
映射关系:
- 利用
HashMap
建立数字到字母的映射关系,方便根据输入的数字找到对应的字母组合。
- 利用
-
字符串处理:
- 使用
StringBuffer
来动态构建字符串,它比普通字符串更高效,因为它允许修改。
- 使用
-
递归终止条件:
- 当递归的深度等于输入数字字符串的长度时,表示已经构建了一个完整的组合,此时将组合添加到结果列表中。
-
循环与递归结合:
- 在递归函数中,通过一个循环遍历当前数字对应的每个字母,并在每次循环中递归调用自身。
-
状态重置:
- 在递归返回后,通过
combination.deleteCharAt(index)
撤销上一次的选择,以便尝试其他可能的字母。
- 在递归返回后,通过
-
参数传递:
- 递归函数中通过参数传递当前的状态,包括结果列表、映射表、输入字符串、当前索引和当前组合。
-
边界条件检查:
- 在主函数
letterCombinations
中,首先检查输入字符串是否为空,为空则直接返回空列表。
- 在主函数
-
时间复杂度:
- 算法的时间复杂度是O(4^n),其中n是输入字符串的长度,因为每个数字最多对应4个字母。
-
空间复杂度:
- 空间复杂度主要取决于递归调用的深度和结果列表的大小,最坏情况下为O(4^n)。