友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
17. Letter Combinations of a Phone Number
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
Input: "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
解题分析
这道题可以使用回溯来解决：每次取出一个数字对应的字母列表，遍历追加到上一次的字母组合中。依次进行，直到数字取完为止。
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
private List<String> result = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if (Objects.isNull(digits) || digits.length() == 0) {
return result;
}
backtrack(digits, "");
return result;
}
private void backtrack(String digits, String letters) {
if (digits.length() == 0) {
result.add(letters);
return;
}
String let = getLetterByChar(digits.charAt(0));
String sub = digits.substring(1);
if (let.length() > 0) {
for (int i = 0; i < let.length(); i++) {
backtrack(sub, letters + let.charAt(i));
}
} else {
backtrack(sub, letters);
}
}
private String getLetterByChar(char c) {
switch (c) {
case '2':
return "abc";
case '3':
return "def";
case '4':
return "ghi";
case '5':
return "jkl";
case '6':
return "mno";
case '7':
return "pqrs";
case '8':
return "tuv";
case '9':
return "wxyz";
default:
return "";
}
}
/**
* Runtime: 32 ms, faster than 6.94% of Java online submissions for Letter Combinations of a Phone Number.
*
* Memory Usage: 36.2 MB, less than 99.10% of Java online submissions for Letter Combinations of a Phone Number.
*/
public List<String> letterCombinations1(String digits) {
if (Objects.isNull(digits) || digits.length() == 0) {
return Collections.EMPTY_LIST;
}
char[] chars = digits.toCharArray();
List<Integer> integers = new ArrayList<>();
int length = chars.length;
for (int i = 0; i < length; i++) {
int num = chars[i] - '0';
if (num > 1) {
integers.add(num);
}
}
char[][] int2chars = new char[][]{
{},
{},
{'a', 'b', 'c'},
{'d', 'e', 'f'},
{'g', 'h', 'i'},
{'j', 'k', 'l'},
{'m', 'n', 'o'},
{'p', 'q', 'r', 's'},
{'t', 'u', 'v'},
{'w', 'x', 'y', 'z'},
};
int size = integers.size();
char[][] selectedChars = new char[size][];
for (int i = 0; i < size; i++) {
selectedChars[i] = int2chars[integers.get(i)];
}
return combine(selectedChars, 0);
}
public List<String> combine(char[][] chars, int depth) {
List<String> result = new ArrayList<>();
char[] rowChars = chars[depth];
if (depth == chars.length - 1) {
for (int i = 0; i < rowChars.length; i++) {
result.add(rowChars[i] + "");
}
} else {
List<String> strings = combine(chars, depth + 1);
for (int i = 0; i < rowChars.length; i++) {
char aChar = rowChars[i];
strings.forEach(s -> result.add(aChar + s));
}
}
return result;
}