-
Notifications
You must be signed in to change notification settings - Fork 83
/
WordLadderII126.java
273 lines (230 loc) · 9.43 KB
/
WordLadderII126.java
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
/**
* Given two words (beginWord and endWord), and a dictionary's word list, find
* all shortest transformation sequence(s) from beginWord to endWord, such that:
*
* Only one letter can be changed at a time
* Each transformed word must exist in the word list. Note that beginWord is
* not a transformed word.
*
* Note:
* Return an empty list if there is no such transformation sequence.
* All words have the same length.
* All words contain only lowercase alphabetic characters.
* You may assume no duplicates in the word list.
* You may assume beginWord and endWord are non-empty and are not the same.
*
* Example 1:
* Input:
* beginWord = "hit",
* endWord = "cog",
* wordList = ["hot","dot","dog","lot","log","cog"]
* Output:
* [
* ["hit","hot","dot","dog","cog"],
* ["hit","hot","lot","log","cog"]
* ]
*
* Example 2:
* Input:
* beginWord = "hit"
* endWord = "cog"
* wordList = ["hot","dot","dog","lot","log"]
* Output: []
*
* Explanation: The endWord "cog" is not in wordList, therefore no possible
* transformation.
*/
public class WordLadderII126 {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Set<String> wordDict = new HashSet<>(wordList);
if (!wordDict.contains(endWord)) return new ArrayList<>();
wordDict.remove(beginWord);
Set<String> visited = new HashSet<>();
List<String> first = new ArrayList<>();
first.add(beginWord);
List<List<String>> res = new ArrayList<>();
res.add(first);
while (true) {
List<List<String>> newRes = new ArrayList<>();
Set<String> localVisited = new HashSet<>();
boolean found = false;
for (int i=0; i<res.size(); i++) {
List<String> path = res.get(i);
String word = path.get(path.size()-1);
for (int j=0; j<word.length(); j++) {
char[] chars = word.toCharArray();
for (char ch='a'; ch<='z'; ch++) {
chars[j] = ch;
String newWord = new String(chars);
if (newWord.equals(endWord)) found = true;
if (!visited.contains(newWord) && wordDict.contains(newWord)) {
List<String> newPath = new ArrayList<>(path);
newPath.add(newWord);
newRes.add(newPath);
if (!newWord.equals(endWord)) localVisited.add(newWord);
// wordDict.remove(newWord);
}
}
}
}
if (newRes.size() == 0) return newRes;
if (found) {
List<List<String>> returned = new ArrayList<>();
for (List<String> p: newRes) {
if (p.get(p.size()-1).equals(endWord)) {
returned.add(p);
}
}
return returned;
}
res = newRes;
visited.addAll(localVisited);
}
}
/**
* https://leetcode.com/problems/word-ladder-ii/discuss/40477/Super-fast-Java-solution-(two-end-BFS)
*/
public List<List<String>> findLadders2(String start, String end, List<String> wordList) {
Set<String> dict = new HashSet<String>(wordList);
if (!dict.contains(end)) return new ArrayList<>();
// hash set for both ends
Set<String> set1 = new HashSet<String>();
Set<String> set2 = new HashSet<String>();
// initial words in both ends
set1.add(start);
set2.add(end);
// we use a map to help construct the final result
Map<String, List<String>> map = new HashMap<String, List<String>>();
// build the map
helper(dict, set1, set2, map, false);
List<List<String>> res = new ArrayList<List<String>>();
List<String> sol = new ArrayList<String>(Arrays.asList(start));
// recursively build the final result
generateList(start, end, map, sol, res);
return res;
}
private boolean helper(Set<String> dict, Set<String> set1, Set<String> set2, Map<String, List<String>> map, boolean flip) {
if (set1.isEmpty()) {
return false;
}
if (set1.size() > set2.size()) {
return helper(dict, set2, set1, map, !flip);
}
// remove words on current both ends from the dict
dict.removeAll(set1);
dict.removeAll(set2);
// as we only need the shortest paths
// we use a boolean value help early termination
boolean done = false;
// set for the next level
Set<String> set = new HashSet<String>();
// for each string in end 1
for (String str : set1) {
for (int i = 0; i < str.length(); i++) {
char[] chars = str.toCharArray();
// change one character for every position
for (char ch = 'a'; ch <= 'z'; ch++) {
chars[i] = ch;
String word = new String(chars);
// make sure we construct the tree in the correct direction
String key = flip ? word : str;
String val = flip ? str : word;
List<String> list = map.containsKey(key) ? map.get(key) : new ArrayList<String>();
if (set2.contains(word)) {
done = true;
list.add(val);
map.put(key, list);
}
if (!done && dict.contains(word)) {
set.add(word);
list.add(val);
map.put(key, list);
}
}
}
}
// early terminate if done is true
return done || helper(dict, set2, set, map, !flip);
}
private void generateList(String start, String end, Map<String, List<String>> map, List<String> sol, List<List<String>> res) {
if (start.equals(end)) {
res.add(new ArrayList<String>(sol));
return;
}
// need this check in case the diff between start and end happens to be one
// e.g "a", "c", {"a", "b", "c"}
if (!map.containsKey(start)) {
return;
}
for (String word : map.get(start)) {
sol.add(word);
generateList(word, end, map, sol, res);
sol.remove(sol.size() - 1);
}
}
List<List<String>> ans = new ArrayList<>();
public List<List<String>> findLadders3(String beginWord, String endWord, List<String> wordList) {
// for each level,
// should NOT use the words in upper level
// should NOT add same words into queue
// however, should use the same word in current level
Map<String, List<String>> map = new HashMap<>();
Set<String> unvisited = new HashSet<>(wordList);
Set<String> visited = new HashSet<>();
Deque<String> queue = new LinkedList<>();
queue.offer(beginWord);
visited.add(beginWord);
unvisited.remove(beginWord);
boolean found = false;
while(!found && !queue.isEmpty()){
// begin each level
int size = queue.size();
visited.clear();
for(int k = 0; k < size; k++){
String word = queue.poll();
for(int i = 0; i < word.length(); i++){
StringBuilder sb = new StringBuilder(word);
for(char c = 'a'; c < 'z'; c++){
sb.setCharAt(i, c);
String newWord = sb.toString();
if(unvisited.contains(newWord)){
if(visited.add(newWord)){
queue.offer(newWord);
}
if(map.containsKey(newWord)){
map.get(newWord).add(word);
}else{
List<String> adj = new ArrayList<>();
adj.add(word);
map.put(newWord, adj);
}
if(newWord.equals(endWord)){
found = true;
}
}
}
}
}
// end of each level
unvisited.removeAll(visited);
}
List<String> path = new ArrayList<>();
path.add(endWord);
dfs(beginWord, path, map);
return ans;
}
private void dfs(String beginWord, List<String> path, Map<String, List<String>> map){
String word = path.get(0);
if(word.equals(beginWord)){
ans.add(new ArrayList<>(path));
return;
}
if(map.containsKey(word)){
for(String prevWord : map.get(word)){
path.add(0, prevWord);
dfs(beginWord, path, map);
path.remove(0);
}
}
}
}