盒子
盒子
文章目录
  1. 17. 电话号码的字母组合

17_电话号码的字母组合_leetcode

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

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

电话号码的字母组合

输入:”23”
输出:[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

题解: 利用队列先进先出特性求解,类似二叉树的层次遍历求解方式,建议断点调试理解求解过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {

public List<String> letterCombinations(String digits) {
LinkedList<String> result = new LinkedList<>();
if (digits == null || digits.isEmpty()) {
return result;
}
// 数字为下标,值为数字可对应的字母
String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

result.add("");
for (int i = 0; i < digits.length(); i++) {
int digit = Character.getNumericValue(digits.charAt(i));
// 控制出入队列内容, 长度为i+1的数字组合依赖于长度为i的组合 + 该数字可对应的字母
while (result.peek().length() == i) {
String prevValue = result.remove(); // 长度为i的组合出队列
for (char c : mapping[digit].toCharArray()) { // 该数字可对应的字母
result.add(prevValue + c); // 长度为i+1的数字组合入队列
}
}
}

return result;
}
}

AC传送门leetcode

支持一下
扫一扫,支持沈健
  • 微信扫一扫
  • 支付宝扫一扫