友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
17. 电话号码的字母组合
给定一个仅包含数字 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']的一个数字。
思路分析
这道题可以使用回溯来解决：每次取出一个数字对应的字母列表，遍历追加到上一次的字母组合中。依次进行，直到数字取完为止。
-
一刷
-
二刷
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
106
107
108
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2019-07-19 00:19
*/
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;
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-12-04 21:56:19
*/
public List<String> letterCombinations(String digits) {
if (digits == null || digits.isEmpty()) {
return Collections.emptyList();
}
List<String> result = new ArrayList<>();
Map<Character, char[]> map = Map.of(
'2', new char[]{'a', 'b', 'c'},
'3', new char[]{'d', 'e', 'f'},
'4', new char[]{'g', 'h', 'i'},
'5', new char[]{'j', 'k', 'l'},
'6', new char[]{'m', 'n', 'o'},
'7', new char[]{'p', 'q', 'r', 's'},
'8', new char[]{'t', 'u', 'v'},
'9', new char[]{'w', 'x', 'y', 'z'}
);
StringBuilder path = new StringBuilder();
backtrack(result, digits.toCharArray(), 0, map, path);
return result;
}
private void backtrack(List<String> result, char[] chars, int index,
Map<Character, char[]> map, StringBuilder path) {
if (chars.length - index + path.length() < chars.length) {
return;
}
if (path.length() == chars.length) {
result.add(path.toString());
}
for (int i = index; i < chars.length; i++) {
for (char c : map.get(chars[i])) {
path.append(c);
backtrack(result, chars, i + 1, map, path);
path.deleteCharAt(path.length() - 1);
}
}
}