Skip to content

Commit 5f5da27

Browse files
fishercoder1534fishercoder1534
committed
refactor 126
1 parent 3351fb7 commit 5f5da27

File tree

1 file changed

+85
-83
lines changed
  • src/main/java/com/fishercoder/solutions

1 file changed

+85
-83
lines changed

‎src/main/java/com/fishercoder/solutions/_126.java

Lines changed: 85 additions & 83 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,5 @@
11
package com.fishercoder.solutions;
22

3-
43
import java.util.ArrayDeque;
54
import java.util.ArrayList;
65
import java.util.HashMap;
@@ -11,9 +10,9 @@
1110

1211
/**
1312
* 126. Word Ladder II
14-
*
15-
* Given two words (beginWord and endWord), and a dictionary's word list,
16-
* find all shortest transformation sequence(s) from beginWord to endWord, such that:
13+
14+
Given two words (beginWord and endWord), and a dictionary's word list,
15+
find all shortest transformation sequence(s) from beginWord to endWord, such that:
1716
1817
Only one letter can be changed at a time
1918
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
@@ -37,106 +36,109 @@
3736
You may assume no duplicates in the word list.
3837
You may assume beginWord and endWord are non-empty and are not the same.
3938
*/
39+
4040
public class _126 {
41-
/**Reference: https://discuss.leetcode.com/topic/2857/share-two-similar-java-solution-that-accpted-by-oj*/
4241

43-
Map<String, List<String>> map;
44-
List<List<String>> results;
42+
public static class Solution1 {
43+
/** Reference: https://discuss.leetcode.com/topic/2857/share-two-similar-java-solution-that-accpted-by-oj */
4544

46-
public List<List<String>> findLadders(String start, String end, List<String> dict) {
47-
results = new ArrayList<>();
48-
if (dict.size() == 0) {
49-
return results;
50-
}
45+
Map<String, List<String>> map;
46+
List<List<String>> results;
5147

52-
int min = Integer.MAX_VALUE;
48+
public List<List<String>> findLadders(String start, String end, List<String> dict) {
49+
results = new ArrayList<>();
50+
if (dict.size() == 0) {
51+
return results;
52+
}
5353

54-
Queue<String> queue = new ArrayDeque<>();
55-
queue.add(start);
54+
int min = Integer.MAX_VALUE;
5655

57-
map = new HashMap<>();
56+
Queue<String> queue = new ArrayDeque<>();
57+
queue.add(start);
5858

59-
Map<String, Integer> ladder = new HashMap<>();
60-
for (String string : dict) {
61-
ladder.put(string, Integer.MAX_VALUE);
62-
}
63-
ladder.put(start, 0);
59+
map = new HashMap<>();
6460

65-
dict.add(end);
66-
//BFS: Dijisktra search
67-
while (!queue.isEmpty()) {
61+
Map<String, Integer> ladder = new HashMap<>();
62+
for (String string : dict) {
63+
ladder.put(string, Integer.MAX_VALUE);
64+
}
65+
ladder.put(start, 0);
6866

69-
String word = queue.poll();
67+
dict.add(end);
68+
//BFS: Dijisktra search
69+
while (!queue.isEmpty()) {
7070

71-
int step = ladder.get(word) + 1;//'step' indicates how many steps are needed to travel to one word.
71+
String word = queue.poll();
7272

73-
if (step > min) {
74-
break;
75-
}
73+
int step = ladder.get(word)
74+
+ 1;//'step' indicates how many steps are needed to travel to one word.
7675

77-
for (int i = 0; i < word.length(); i++) {
78-
StringBuilder builder = new StringBuilder(word);
79-
for (char ch = 'a'; ch <= 'z'; ch++) {
80-
builder.setCharAt(i, ch);
81-
String newWord = builder.toString();
82-
if (ladder.containsKey(newWord)) {
83-
84-
if (step > ladder.get(newWord)) {
85-
//Check if it is the shortest path to one word.
86-
continue;
87-
} else if (step < ladder.get(newWord)) {
88-
queue.add(newWord);
89-
ladder.put(newWord, step);
90-
} else {
91-
// It is a KEY line. If one word already appeared in one ladder,
92-
// Do not insert the same word inside the queue twice. Otherwise it gets TLE.
93-
}
94-
if (map.containsKey(newWord)) {
95-
//Build adjacent Graph
96-
map.get(newWord).add(word);
97-
} else {
98-
List<String> list = new LinkedList();
99-
list.add(word);
100-
map.put(newWord, list);
101-
//It is possible to write three lines in one:
102-
//map.put(new_word,new LinkedList<String>(Arrays.asList(new String[]{word})));
103-
//Which one is better?
104-
}
76+
if (step > min) {
77+
break;
78+
}
10579

106-
if (newWord.equals(end)) {
107-
min = step;
80+
for (int i = 0; i < word.length(); i++) {
81+
StringBuilder builder = new StringBuilder(word);
82+
for (char ch = 'a'; ch <= 'z'; ch++) {
83+
builder.setCharAt(i, ch);
84+
String newWord = builder.toString();
85+
if (ladder.containsKey(newWord)) {
86+
87+
if (step > ladder.get(newWord)) {
88+
//Check if it is the shortest path to one word.
89+
continue;
90+
} else if (step < ladder.get(newWord)) {
91+
queue.add(newWord);
92+
ladder.put(newWord, step);
93+
} else {
94+
// It is a KEY line. If one word already appeared in one ladder,
95+
// Do not insert the same word inside the queue twice. Otherwise it gets TLE.
96+
}
97+
if (map.containsKey(newWord)) {
98+
//Build adjacent Graph
99+
map.get(newWord).add(word);
100+
} else {
101+
List<String> list = new LinkedList();
102+
list.add(word);
103+
map.put(newWord, list);
104+
//It is possible to write three lines in one:
105+
//map.put(new_word,new LinkedList<String>(Arrays.asList(new String[]{word})));
106+
//Which one is better?
107+
}
108+
109+
if (newWord.equals(end)) {
110+
min = step;
111+
}
108112
}
109-
113+
//End if dict contains new_word
110114
}
111-
//End if dict contains new_word
115+
//End:Iteration from 'a' to 'z'
112116
}
113-
//End:Iteration from 'a' to 'z'
117+
//End:Iteration from the first to the last
114118
}
115-
//End:Iteration from the first to the last
116-
}
117-
//End While
118-
119-
//BackTracking
120-
LinkedList<String> result = new LinkedList<>();
121-
backTrace(end, start, result);
119+
//End While
122120

123-
return results;
124-
}
121+
//BackTracking
122+
LinkedList<String> result = new LinkedList<>();
123+
backTrace(end, start, result);
125124

126-
private void backTrace(String word, String start, List<String> list) {
127-
if (word.equals(start)) {
128-
list.add(0, start);
129-
results.add(new ArrayList<>(list));
130-
list.remove(0);
131-
return;
125+
return results;
132126
}
133-
list.add(0, word);
134-
if (map.get(word) != null) {
135-
for (String s : map.get(word)) {
136-
backTrace(s, start, list);
127+
128+
private void backTrace(String word, String start, List<String> list) {
129+
if (word.equals(start)) {
130+
list.add(0, start);
131+
results.add(new ArrayList<>(list));
132+
list.remove(0);
133+
return;
134+
}
135+
list.add(0, word);
136+
if (map.get(word) != null) {
137+
for (String s : map.get(word)) {
138+
backTrace(s, start, list);
139+
}
137140
}
141+
list.remove(0);
138142
}
139-
list.remove(0);
140143
}
141-
142144
}

0 commit comments

Comments
 (0)