A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 126. Word Ladder II, the solution in this repository is mainly a graph traversal solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: graph traversal, backtracking.
The notes already sitting in the source point us in the right direction:
- TLE
- 21 / 39 test cases passed.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are connected, backtrack, visited, getNextLevel, buildGraph.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//TLE
02//21 / 39 test cases passed.
03class Solution {
04public:
05 string beginWord, endWord;
06 vector<vector<int>> adjList;
07 int minLen;
08 int start, end;
09
10 bool connected(string& s1, string& s2){
11 int m = s1.size();
12 int n = s2.size();
13 if(m != n) return -1;
14
15 int count = 0;
16 for(int i = 0; i < m; ++i){
17 if(s1[i] != s2[i]){
18 ++count;
19 if(count > 1) return false;
20 }
21 }
22 return count == 1;
23 };
24
25 void backtrack(int cur, vector<string>& wordList, vector<bool>& visited, vector<string>& path, vector<vector<string>>& paths){
26 if(path.size() > minLen){
27 // cout << "early stopping" << endl;
28 return;
29 }else if(!path.empty() && path.back() == endWord){
30 // cout << "push" << endl;
31 if(paths.empty() || path.size() == minLen){
32 minLen = path.size();
33 paths.push_back(path);
34 }else{
35 //path.size() < minLen
36 minLen = path.size();
37 paths.clear();
38 paths.push_back(path);
39 }
40 }else{
41 // cout << "building" << endl;
42 for(int nei : adjList[cur]){
43 visited[nei] = true;
44 path.push_back(wordList[nei]);
45 backtrack(nei, wordList, visited, path, paths);
46 visited[nei] = false;
47 path.pop_back();
48 }
49 }
50 };
51
52 vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
53 this->beginWord = beginWord;
54 this->endWord = endWord;
55 auto it = find(wordList.begin(), wordList.end(), beginWord);
56 int start;
57 if(it == wordList.end()){
58 wordList.push_back(beginWord);
59 start = wordList.size()-1;
60 }else{
61 start = it - wordList.begin();
62 }
63
64 it = find(wordList.begin(), wordList.end(), endWord);
65 if(it == wordList.end()) return vector<vector<string>>();
66 int end = it - wordList.begin();
67
68 // cout << "start: " << start << ", end: " << end << endl;
69
70 int n = wordList.size();
71
72 adjList = vector<vector<int>>(n);
73
74 for(int i = 0; i < n; ++i){
75 for(int j = i+1; j < n; ++j){
76 if(connected(wordList[i], wordList[j])){
77 adjList[i].push_back(j);
78 adjList[j].push_back(i);
79 }
80 }
81 }
82
83 minLen = wordList.size();
84 vector<bool> visited(n, false);
85 vector<string> path = {beginWord};
86 vector<vector<string>> paths;
87
88 backtrack(start, wordList, visited, path, paths);
89
90 return paths;
91 }
92};
93
94//BFS + DFS(backtracking)
95//https://leetcode.com/problems/word-ladder-ii/discuss/40475/My-concise-JAVA-solution-based-on-BFS-and-DFS/145572
96//TLE
97//29 / 39 test cases passed.
98class Solution {
99public:
100 int n;
101
102 void getNextLevel(int begin, vector<string>& wordList, vector<int>& neighbors){
103 string beginWord = wordList[begin];
104 vector<string>::iterator it;
105
106 for(int i = 0; i < beginWord.size(); ++i){
107 for(char c = 'a'; c <= 'z'; ++c){
108 if(beginWord[i] == c) continue;
109 char oldC = beginWord[i];
110 beginWord[i] = c;
111 if((it = find(wordList.begin(), wordList.end(), beginWord)) !=
112 wordList.end()){
113 // cout << wordList[it - wordList.begin()] << " ";
114 neighbors.push_back(it - wordList.begin());
115 }
116 beginWord[i] = oldC;
117 }
118 }
119
120 // cout << endl;
121 };
122
123 void buildGraph(int begin, int end, vector<string>& wordList, unordered_map<int, unordered_set<int>>& graph){
124 unordered_set<int> visited, tovisit;
125
126 queue<int> q;
127 //0th level
128 q.push(begin);
129 // tovisit.insert(begin); //don't need this
130 tovisit.insert(begin);
131
132 bool foundEnd = false;
133
134 while(!q.empty()){
135 visited.insert(tovisit.begin(), tovisit.end());
136 tovisit.clear();
137
138 int levelSize = q.size();
139
140 for(int i = 0; i < levelSize; ++i){
141 int cur = q.front(); q.pop();
142
143 // cout << "cur: " << wordList[cur] << ", neighbors: ";
144
145 vector<int> neighbors;
146 getNextLevel(cur, wordList, neighbors);
147
148 // cout << "found " << neighbors.size() << " neighbors." << endl;
149
150 for(int nei : neighbors){
151 if(nei == end) foundEnd = true;
152 // if(!visited[nei]){
153 if(visited.find(nei) == visited.end()){
154 //there could be a duplicate, so we use set
155 graph[cur].insert(nei);
156 // cout << "nei: " << wordList[nei] << endl;
157 }
158
159 /*
160 in a graph, a node can be reached from multiple parents,
161 so we use the "tovisit" to avoid
162 visiting the same node in the same level twice
163 */
164 // if(!visited[nei] && !tovisit[nei]){
165 if(visited.find(nei) == visited.end() && tovisit.find(nei) == tovisit.end()){
166 q.push(nei);
167 // cout << "to visit " << wordList[nei] << endl;
168 // tovisit[nei] = true;
169 tovisit.insert(nei);
170 }
171 }
172 // cout << endl;
173 }
174
175 //stopping building graph once we find the goal
176 if(foundEnd) break;
177 }
178 // cout << endl;
179 };
180
181 void dfs(int cur, int end, vector<string>& wordList,
182 unordered_map<int, unordered_set<int>>& graph,
183 vector<string>& path, vector<vector<string>>& paths){
184 path.push_back(wordList[cur]);
185
186 if(cur == end){
187 paths.push_back(path);
188 }else{
189 for(int nei : graph[cur]){
190 dfs(nei, end, wordList, graph, path, paths);
191 }
192 }
193
194 path.pop_back();
195 }
196
197 void backtrack(int cur, int end, vector<string>& wordList,
198 unordered_map<int, unordered_set<int>>& graph,
199 vector<string>& path, vector<vector<string>>& paths){
200 if(cur == end){
201 paths.push_back(path);
202 }else{
203 for(int nei : graph[cur]){
204 // cout << wordList[cur] << " -> " << wordList[nei] << endl;
205 path.push_back(wordList[nei]);
206 backtrack(nei, end, wordList, graph, path, paths);
207 path.pop_back();
208 }
209 }
210 }
211
212 vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
213 int begin, end;
214
215 auto it = find(wordList.begin(), wordList.end(), beginWord);
216 if(it != wordList.end()){
217 begin = it - wordList.begin();
218 }else{
219 wordList.push_back(beginWord);
220 begin = wordList.size()-1;
221 }
222
223 it = find(wordList.begin(), wordList.end(), endWord);
224 if(it != wordList.end()){
225 end = it - wordList.begin();
226 }else{
227 return vector<vector<string>>();
228 }
229
230 n = wordList.size();
231 vector<string> path;
232 vector<vector<string>> paths;
233 unordered_map<int, unordered_set<int>> graph;
234
235 // cout << "begin: " << begin << ", end: " << end << ", n: " << n << endl;
236
237 buildGraph(begin, end, wordList, graph);
238
239 // for(int i = 0; i < n; ++i){
240 // cout << wordList[i] << " has " << graph[i].size() << " neighbors: ";
241 // for(int j : graph[i]){
242 // cout << wordList[j] << " ";
243 // }
244 // cout << endl;
245 // }
246 // dfs(begin, end, wordList, graph, path, paths);
247 path = {wordList[begin]};
248 backtrack(begin, end, wordList, graph, path, paths);
249
250 return paths;
251 }
252};
253
254//revised from above, represent wordList as unordered_set
255//Runtime: 324 ms, faster than 73.15% of C++ online submissions for Word Ladder II.
256//Memory Usage: 32.5 MB, less than 69.39% of C++ online submissions for Word Ladder II.
257class Solution {
258public:
259 int n;
260
261 void getNextLevel(string& beginWord, unordered_set<string>& wordList, vector<string>& neighbors){
262 vector<string>::iterator it;
263
264 for(int i = 0; i < beginWord.size(); ++i){
265 for(char c = 'a'; c <= 'z'; ++c){
266 if(beginWord[i] == c) continue;
267 char oldC = beginWord[i];
268 beginWord[i] = c;
269 if(wordList.find(beginWord) != wordList.end()){
270 neighbors.push_back(beginWord);
271 }
272 beginWord[i] = oldC;
273 }
274 }
275 };
276
277 void buildGraph(string& beginWord, string& endWord, unordered_set<string>& wordList, unordered_map<string, unordered_set<string>>& graph){
278 unordered_set<string> visited, tovisit;
279
280 queue<string> q;
281 q.push(beginWord);
282 tovisit.insert(beginWord);
283
284 bool foundEnd = false;
285
286 while(!q.empty()){
287 visited.insert(tovisit.begin(), tovisit.end());
288 tovisit.clear();
289
290 int levelSize = q.size();
291
292 for(int i = 0; i < levelSize; ++i){
293 string cur = q.front(); q.pop();
294
295 vector<string> neighbors;
296 getNextLevel(cur, wordList, neighbors);
297
298 for(string nei : neighbors){
299 if(nei == endWord) foundEnd = true;
300 if(visited.find(nei) == visited.end()){
301 graph[cur].insert(nei);
302 }
303
304 if(visited.find(nei) == visited.end() && tovisit.find(nei) == tovisit.end()){
305 q.push(nei);
306 tovisit.insert(nei);
307 }
308 }
309 }
310
311 if(foundEnd) break;
312 }
313 };
314
315 void backtrack(string& cur, string& endWord, unordered_set<string>& wordList,
316 unordered_map<string, unordered_set<string>>& graph,
317 vector<string>& path, vector<vector<string>>& paths){
318 if(cur == endWord){
319 paths.push_back(path);
320 }else{
321 for(string nei : graph[cur]){
322 path.push_back(nei);
323 backtrack(nei, endWord, wordList, graph, path, paths);
324 path.pop_back();
325 }
326 }
327 }
328
329 vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
330 auto it = find(wordList.begin(), wordList.end(), beginWord);
331 if(it == wordList.end()){
332 wordList.push_back(beginWord);
333 }
334
335 it = find(wordList.begin(), wordList.end(), endWord);
336 if(it == wordList.end()){
337 return vector<vector<string>>();
338 }
339
340 unordered_set<string> words(wordList.begin(), wordList.end());
341
342 n = words.size();
343 vector<string> path;
344 vector<vector<string>> paths;
345 unordered_map<string, unordered_set<string>> graph;
346
347 buildGraph(beginWord, endWord, words, graph);
348
349 path = {beginWord};
350 backtrack(beginWord, endWord, words, graph, path, paths);
351
352 return paths;
353 }
354};
355
356
357
358//BFS, view a path as a node
359//https://leetcode.com/problems/word-ladder-ii/discuss/40434/C%2B%2B-solution-using-standard-BFS-method-no-DFS-or-backtracking
360//Runtime: 968 ms, faster than 43.36% of C++ online submissions for Word Ladder II.
361//Memory Usage: 180.1 MB, less than 28.57% of C++ online submissions for Word Ladder II.
362class Solution {
363public:
364 vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
365 int level = 1;
366 int minLevel = INT_MAX;
367 queue<vector<string>> q;
368 vector<vector<string>> ans;
369 unordered_set<string> visited;
370
371 //represent vector as unordered_set is the key to avoid TLE!!!
372 unordered_set<string> words(wordList.begin(), wordList.end());
373
374 q.push({beginWord});
375
376 while(!q.empty()){
377 vector<string> path = q.front(); q.pop();
378
379 if(path.size() > minLevel){
380 break;
381 }
382
383 if(path.size() > level){
384 // visited.clear(); //add this line will make it slower
385 //reach a new level, erase the unneeded words
386 for(const string& word : visited){
387 words.erase(word);
388 }
389
390 level = path.size();
391 }
392
393 string cur = path.back();
394
395 if(cur == endWord){
396 minLevel = level;
397 ans.push_back(path);
398 }
399
400 for(int i = 0; i < cur.size(); ++i){
401 char oldC = cur[i];
402
403 for(char c = 'a'; c <= 'z'; ++c){
404 if(c == oldC) continue;
405 cur[i] = c;
406
407 if(words.find(cur) != words.end()){
408 vector<string> nextpath = path;
409 nextpath.push_back(cur);
410 visited.insert(cur);
411 q.push(nextpath);
412 }
413 }
414
415 cur[i] = oldC;
416 }
417 }
418
419 return ans;
420 }
421};
422
423//Bidirectional Breadth First Search
424//https://leetcode.com/problems/word-ladder-ii/discuss/269012/Python-BFS%2BBacktrack-Greatly-Improved-by-bi-directional-BFS
425//Runtime: 68 ms, faster than 93.13% of C++ online submissions for Word Ladder II.
426//Memory Usage: 15.8 MB, less than 97.96% of C++ online submissions for Word Ladder II.
427class Solution {
428public:
429 void backtrack(string cur, string& endWord, unordered_map<string, unordered_set<string>>& graph,
430 vector<string>& path, vector<vector<string>>& paths){
431 //cout << "cur: " << cur << endl;
432 if(cur == endWord){
433 paths.push_back(path);
434 }else{
435 //cout << "neighbors: " << graph[cur].size() << endl;
436 for(const string& nei : graph[cur]){
437 path.push_back(nei);
438 backtrack(nei, endWord, graph, path, paths);
439 path.pop_back();
440 }
441 }
442 };
443
444 bool visitLevel(unordered_set<string>& words, unordered_map<string, unordered_set<string>>& graph,
445 queue<string>& q, unordered_set<string>& visited, unordered_set<string>& visited_other, bool reversed){
446 int levelSize = q.size();
447 bool foundEnd = false;
448 unordered_set<string> visiting;
449
450 //visited: visited node for previous levels
451 //visiting: the nodes visit in current level
452
453 while(levelSize-- > 0){
454 string cur = q.front(); q.pop();
455 //cout << cur << " : ";
456
457 string nei = cur;
458
459 for(int i = 0; i < cur.size(); ++i){
460 char oldC = nei[i];
461 for(char c = 'a'; c <= 'z'; ++c){
462 if(c == oldC) continue;
463 nei[i] = c;
464
465 if(words.find(nei) != words.end()){
466 if(visited_other.find(nei) != visited_other.end()){
467 //cout << "found end ";
468 foundEnd = true;
469 }
470
471 //if nei isn't in previous levels
472 if(visited.find(nei) == visited.end()){
473 /*
474 Here we don't mark "nei" as "visited",
475 because we want that "nei" can be visited by
476 multiple nodes in current level!!!
477 */
478 visiting.insert(nei);
479 q.push(nei);
480
481 if(!reversed){
482 graph[cur].insert(nei);
483 }else{
484 graph[nei].insert(cur);
485 }
486 //cout << nei << " ";
487 }
488 }
489
490 }
491 nei[i] = oldC;
492 }
493 //cout << endl;
494 }
495
496 //the nodes in visiting are actually visited in current level
497 visited.insert(visiting.begin(), visiting.end());
498
499 return foundEnd;
500 };
501
502 vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
503 unordered_set<string> words(wordList.begin(), wordList.end());
504 unordered_map<string, unordered_set<string>> graph;
505 int n = words.size();
506
507 if(words.find(endWord) == words.end()) return vector<vector<string>>();
508
509 //cout << "word: ";
510 //for(const string& word : words){
511 // cout << word << " ";
512 //}
513 //cout << endl;
514
515 bool foundEnd = false;
516 queue<string> q1, q2;
517 unordered_set<string> visited1, visited2;
518 queue<string> qnext;
519 bool reversed = false;
520
521 q1.push(beginWord);
522 q2.push(endWord);
523 visited1.insert(beginWord);
524 visited2.insert(endWord);
525
526 while(!q1.empty() && !q2.empty() && !foundEnd){
527 if(q1.size() < q2.size()){
528 //cout << "forward: " << endl;
529 foundEnd = visitLevel(words, graph, q1, visited1, visited2, false);
530 }else{
531 //cout << "backward: " << endl;
532 foundEnd = visitLevel(words, graph, q2, visited2, visited1, true);
533 }
534 }
535
536 //for(auto p : graph){
537 // cout << p.first << " -> ";
538 // for(const string& nei : p.second){
539 // cout << nei << " ";
540 // }
541 // cout << endl;
542 //}
543
544 vector<string> path = {beginWord};
545 vector<vector<string>> paths;
546
547 backtrack(beginWord, endWord, graph, path, paths);
548
549 return paths;
550 }
551};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.