Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitbba1ed1

Browse files
committed
feat: add 017
1 parent5747297 commitbba1ed1

File tree

4 files changed

+147
-1
lines changed

4 files changed

+147
-1
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -61,6 +61,7 @@
6161
|3|[Longest Substring Without Repeating Characters][003]|Hash Table, Two Pointers, String|
6262
|8|[String to Integer (atoi)][008]|Math, String|
6363
|15|[3Sum][015]|Array, Two Pointers|
64+
|17|[Letter Combinations of a Phone Number][017]|String, Backtracking|
6465
|19|[Remove Nth Node From End of List][019]|Linked List, Two Pointers|
6566
|554|[Brick Wall][554]|Hash Table|
6667

@@ -117,6 +118,7 @@
117118
[003]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/003/README.md
118119
[008]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/008/README.md
119120
[015]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/015/README.md
121+
[017]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/017/README.md
120122
[019]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/019/README.md
121123
[554]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/554/README.md
122124

‎note/017/README.md

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
#[Letter Combinations of a Phone Number][title]
2+
3+
##Description
4+
5+
Given a digit string, return all possible letter combinations that the number could represent.
6+
7+
A mapping of digit to letters (just like on the telephone buttons) is given below.
8+
9+
![img](https://upload.wikimedia.org/wikipedia/commons/thumb/7/73/Telephone-keypad2.svg/200px-Telephone-keypad2.svg.png)
10+
11+
```
12+
Input:Digit string "23"
13+
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
14+
15+
```
16+
17+
**Note:**
18+
Although the above answer is in lexicographical order, your answer could be in any order you want.
19+
20+
**Tags:** String, Backtracking
21+
22+
23+
##思路0
24+
25+
题意是给你按键，让你组合出所有不同结果，首先想到的肯定是回溯了，对每个按键的所有情况进行回溯，回溯的终点就是结果字符串长度和按键长度相同。
26+
27+
```java
28+
classSolution {
29+
privatestaticString[] map=newString[]{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
30+
31+
publicList<String>letterCombinations(Stringdigits) {
32+
if (digits.length()==0)returnCollections.emptyList();
33+
List<String> list=newArrayList<>();
34+
helper(list, digits,"");
35+
return list;
36+
}
37+
38+
privatevoidhelper(List<String>list,Stringdigits,Stringans) {
39+
if (ans.length()== digits.length()) {
40+
list.add(ans);
41+
return;
42+
}
43+
for (char c: map[digits.charAt(ans.length())-'2'].toCharArray()) {
44+
helper(list, digits, ans+ c);
45+
}
46+
}
47+
}
48+
```
49+
50+
##思路1
51+
52+
还有一种思路就是利用队列，根据上一次队列中的值，该值拼接当前可选值来不断迭代其结果，具体代码如下。
53+
54+
```java
55+
classSolution {
56+
privatestaticString[] map=newString[]{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
57+
58+
publicList<String>letterCombinations(Stringdigits) {
59+
if (digits.length()==0)returnCollections.emptyList();
60+
LinkedList<String> list=newLinkedList<>();
61+
list.add("");
62+
char[] charArray= digits.toCharArray();
63+
for (int i=0; i< charArray.length; i++) {
64+
char c= charArray[i];
65+
while (list.getFirst().length()== i) {
66+
String pop= list.removeFirst();
67+
for (char v: map[c-'2'].toCharArray()) {
68+
list.addLast(pop+ v);
69+
}
70+
}
71+
}
72+
return list;
73+
}
74+
}
75+
```
76+
77+
78+
##结语
79+
80+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]
81+
82+
83+
84+
[title]:https://leetcode.com/problems/letter-combinations-of-a-phone-number
85+
[ajl]:https://github.com/Blankj/awesome-java-leetcode

‎src/com/blankj/medium/_015/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
* <pre>
99
* author: Blankj
1010
* blog : http://blankj.com
11-
* time : 2017/04/23
11+
* time : 2017/10/14
1212
* desc :
1313
* </pre>
1414
*/
Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
packagecom.blankj.medium._017;
2+
3+
importjava.util.Collections;
4+
importjava.util.LinkedList;
5+
importjava.util.List;
6+
7+
/**
8+
* <pre>
9+
* author: Blankj
10+
* blog : http://blankj.com
11+
* time : 2017/10/15
12+
* desc :
13+
* </pre>
14+
*/
15+
publicclassSolution {
16+
// private static String[] map = new String[]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
17+
//
18+
// public List<String> letterCombinations(String digits) {
19+
// if (digits.length() == 0) return Collections.emptyList();
20+
// List<String> list = new ArrayList<>();
21+
// helper(list, digits, "");
22+
// return list;
23+
// }
24+
//
25+
// private void helper(List<String> list, String digits, String ans) {
26+
// if (ans.length() == digits.length()) {
27+
// list.add(ans);
28+
// return;
29+
// }
30+
// for (char c : map[digits.charAt(ans.length()) - '2'].toCharArray()) {
31+
// helper(list, digits, ans + c);
32+
// }
33+
// }
34+
35+
privatestaticString[]map =newString[]{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
36+
37+
publicList<String>letterCombinations(Stringdigits) {
38+
if (digits.length() ==0)returnCollections.emptyList();
39+
LinkedList<String>list =newLinkedList<>();
40+
list.add("");
41+
char[]charArray =digits.toCharArray();
42+
for (inti =0;i <charArray.length;i++) {
43+
charc =charArray[i];
44+
45+
while (list.getFirst().length() ==i) {
46+
Stringpop =list.removeFirst();
47+
for (charv :map[c -'2'].toCharArray()) {
48+
list.addLast(pop +v);
49+
}
50+
}
51+
}
52+
returnlist;
53+
}
54+
55+
publicstaticvoidmain(String[]args) {
56+
Solutionsolution =newSolution();
57+
System.out.println(solution.letterCombinations("23"));
58+
}
59+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp