【力扣刷题】17. 电话号码的字母组合
17 刷题 力扣 电话号码 字母组合
2023-06-13 09:14:29 时间
一、题目描述
来源:力扣（LeetCode）
给定一个仅包含数字 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 <= 4digits[i]是范围['2', '9']的一个数字。
二、思路分析
我们可以利用队列的先进先出特点，再配合循环完成题目要求。
- 定义一个空字符串来作为起始
- 将2对应的字符"a","b","c"依次放入队列中,这样就变成 "a","b","c"
- 从队列中拿出第一个元素"a"，跟3对应的字符"d","e","f"挨个拼接，队列变成 "b","c","ad","ae","af"
- 按照上面的步骤依次取出下一个元素拼接
三、代码实现
class Solution {
public List<String> letterCombinations(String digits) {
if(digits==null || digits.length()==0) {
return new ArrayList<String>();
}
//一个映射表，第二个位置是"abc“,第三个位置是"def"。。。
//这里也可以用map，用数组可以更节省点内存
String[] letter_map = {
" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
};
List<String> res = new ArrayList<>();
//先往队列中加入一个空字符
res.add("");
for(int i=0;i<digits.length();i++) {
//由当前遍历到的字符，取字典表中查找对应的字符串
String letters = letter_map[digits.charAt(i)-'0'];
int size = res.size();
//计算出队列长度后，将队列中的每个元素挨个拿出来
for(int j=0;j<size;j++) {
//每次都从队列中拿出第一个元素
String tmp = res.remove(0);
//然后跟"def"这样的字符串拼接，并再次放到队列中
for(int k=0;k<letters.length();k++) {
res.add(tmp+letters.charAt(k));
}
}
}
return res;
}
}四、运行结果
总结
一开始我是使用暴力解法，结果发现超时了，参考了别人的队列解法，还有个回溯解法是使用了递归+循环，容易绕进去，故选择队列方式，比较直观.