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

Commit472fd59

Browse files
committed
126 (2) clean up solution
1 parentc34f755 commit472fd59

File tree

5 files changed

+806
-810
lines changed

5 files changed

+806
-810
lines changed

‎src/_126_WordLadderII/Solution.java

Lines changed: 25 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -48,74 +48,70 @@ public class Solution {
4848
* 2. each word is allowed duplicates in the same level but not the previous levels
4949
* 3. use father map to avoid calculating the ladder for the duplicated word in the same level
5050
*/
51-
publicList<List<String>>findLadders(Stringstart,Stringend,
52-
Set<String>dict) {
51+
publicList<List<String>>findLadders(Stringstart,Stringend,Set<String>dict) {
52+
5353
List<List<String>>result =newArrayList<>();
54+
5455
if (start.equals(end)) {
5556
result.add(Arrays.asList(start,end));
5657
returnresult;
5758
}
5859

5960
// use set for current level instead of queue to avoid calculating ladder for duplicated word
60-
Set<String>current =newHashSet<>();
61-
Set<String>next =newHashSet<>();
61+
Set<String>cur =newHashSet<>();
6262
Set<String>visited =newHashSet<>();
63+
// word, and all words that can direct lead to this word in path
6364
Map<String,List<String>>fatherMap =newHashMap<>();
64-
current.add(start);
65+
cur.add(start);
6566

6667
booleanfound =false;
6768
intwordLen =start.length();
6869

69-
while (!current.isEmpty() && !found) {
70-
visited.addAll(current);
71-
// ! should not be next.clear()
72-
// next.clear() will empty the set, which current is also pointed to
73-
// next = new HashSet<>(); will point next to a new empty set
74-
// while keep the originally set which is now pointed by current intact.
75-
next =newHashSet<>();
76-
for (Stringstring :current) {
70+
while (!cur.isEmpty() && !found) {
71+
72+
Set<String>next =newHashSet<>();
73+
74+
for (Stringstr :cur) {
7775
for (inti =0;i <wordLen;i++) {
78-
StringBuilderwordBuilder =newStringBuilder(string);
76+
StringBuildersb =newStringBuilder(str);
7977
for (charch ='a';ch <='z';ch++) {
80-
wordBuilder.setCharAt(i,ch);
81-
Stringword =wordBuilder.toString();
78+
sb.setCharAt(i,ch);
79+
Stringword =sb.toString();
8280
if (word.equals(end)) {
8381
found =true;
8482
}
8583
if (dict.contains(word) && !visited.contains(word)
8684
||word.equals(end)) {
8785
next.add(word);
88-
if (fatherMap.containsKey(word)) {
89-
fatherMap.get(word).add(string);
90-
}else {
91-
List<String>list =newArrayList<>();
92-
list.add(string);
93-
fatherMap.put(word,list);
86+
if (!fatherMap.containsKey(word)) {
87+
fatherMap.put(word,newArrayList<>());
9488
}
89+
fatherMap.get(word).add(str);
9590
}
9691
}
9792
}
9893
}
99-
current =next;
94+
95+
cur =next;
96+
visited.addAll(cur);
10097
}
10198
if (found) {
102-
List<String>res =newArrayList<>();
103-
dfs(result,fatherMap,res,start,end);
99+
List<String>path =newArrayList<>();
100+
dfs(start,end,path,fatherMap,result);
104101
}
105102
returnresult;
106103
}
107104

108-
privatevoiddfs(List<List<String>>result,
109-
Map<String,List<String>>fatherMap,List<String>path,
110-
Stringstart,Stringend) {
105+
// construct paths based father map
106+
privatevoiddfs(Stringstart,Stringend,List<String>path,Map<String,List<String>>fatherMap,List<List<String>>result) {
111107
path.add(end);
112108
if (end.equals(start)) {
113109
result.add(newArrayList<>(path));
114110
Collections.reverse(result.get(result.size() -1));
115111
}else {
116112
List<String>que =fatherMap.get(end);
117113
for (Stringword :que) {
118-
dfs(result,fatherMap,path,start,word);
114+
dfs(start,word,path,fatherMap,result);
119115
}
120116
}
121117
path.remove(path.size() -1);

‎src/_126_WordLadderII/SolutionBottomUp.java

Lines changed: 23 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -42,51 +42,55 @@ public class SolutionBottomUp {
4242

4343
publicList<List<String>>findLadders(Stringstart,Stringend,
4444
Set<String>dict) {
45+
4546
List<List<String>>result =newArrayList<>();
47+
48+
// base case
4649
if (start.equals(end)) {
4750
result.add(Arrays.asList(start,end));
4851
returnresult;
4952
}
5053

51-
Set<String>current =newHashSet<>();
54+
Set<String>cur =newHashSet<>();
5255
// all words that have been visited above current visiting level
5356
Set<String>visited =newHashSet<>();
5457
// <word, all direct fathers of this word in the path>
5558
Map<String,List<String>>fatherMap =newHashMap<>();
56-
current.add(end);
59+
cur.add(end);
5760

5861
booleanfound =false;
59-
intwordLen =start.length();
6062

61-
while (!current.isEmpty() && !found) {
63+
// BFS
64+
while (!cur.isEmpty() && !found) {
6265
Set<String>next =newHashSet<>();
63-
for (Stringstring :current) {
64-
for (inti =0;i <wordLen;i++) {
65-
StringBuilderwordBuilder =newStringBuilder(string);
66+
for (Stringstr :cur) {
67+
for (inti =0;i <str.length();i++) {
6668
for (charch ='a';ch <='z';ch++) {
67-
wordBuilder.setCharAt(i,ch);
68-
Stringword =wordBuilder.toString();
69+
StringBuildersb =newStringBuilder(str);
70+
sb.setCharAt(i,ch);
71+
Stringword =sb.toString();
6972
if (word.equals(start)) {
7073
found =true;
7174
}
72-
if (!found &&dict.contains(word) && !visited.contains(word)
75+
if (!found &&dict.contains(word)
76+
&& !visited.contains(word)
7377
||word.equals(start)) {
7478
next.add(word);
7579
// update father map
76-
if (fatherMap.containsKey(word)) {
77-
fatherMap.get(word).add(string);
78-
}else {
79-
fatherMap.put(word,newArrayList<>(Arrays.asList(string)));
80+
if (!fatherMap.containsKey(word)) {
81+
fatherMap.put(word,newArrayList<>());
8082
}
83+
fatherMap.get(word).add(str);
8184
}
8285
}
8386
}
8487
}
85-
current =next;
86-
// because we allow duplicates in the same level,
88+
cur =next;
89+
// because we allow duplicates in the same level,
8790
// therefore we delay updating visited until we finish current level
88-
visited.addAll(current);
91+
visited.addAll(cur);
8992
}
93+
9094
if (found) {
9195
List<String>path =newArrayList<>();
9296
dfs(result,fatherMap,path,start,end);
@@ -102,11 +106,11 @@ private void dfs(List<List<String>> result,
102106
if (end.equals(start)) {
103107
// base case
104108
result.add(newArrayList<>(path));
105-
// Collections.reverse(result.get(result.size() - 1));
109+
// Collections.reverse(result.get(result.size() - 1));
106110
}else {
107111
// recursive case
108112
List<String>fathers =fatherMap.get(start);
109-
for (Stringfather:fathers) {
113+
for (Stringfather:fathers) {
110114
dfs(result,fatherMap,path,father,end);
111115
}
112116
}

‎src/_126_WordLadderII/SolutionMLE.java

Lines changed: 1 addition & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -43,8 +43,7 @@ public class SolutionMLE {
4343

4444
privateQueue<List<String>>pathsQueue =newLinkedList<>();
4545

46-
publicList<List<String>>findLadders(Stringstart,Stringend,
47-
Set<String>dict) {
46+
publicList<List<String>>findLadders(Stringstart,Stringend,Set<String>dict) {
4847
List<List<String>>result =newArrayList<>();
4948

5049
if (start.equals(end)) {
@@ -87,9 +86,6 @@ public List<List<String>> findLadders(String start, String end,
8786
// update visited until we finish current level
8887
visited.addAll(curWords);
8988
}
90-
// for (List<String> string : result) {
91-
// System.out.println(string);
92-
// }
9389
returnresult;
9490
}
9591

@@ -112,7 +108,6 @@ private List<String> getPossibleWords(String end, List<String> path,
112108
}
113109
}
114110
}
115-
// System.out.println("pos: [" + start + "], " + words);
116111
returnwords;
117112
}
118113

0 commit comments

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