LeetCode - Word Ladder II

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

 1 // 9CE, 1TLE, 1WA, 1AC, O(n^2) will get you TLE, no matter time or space.
 2 #include <string>
 3 #include <unordered_map>
 4 #include <unordered_set>
 5 #include <vector>
 6 using namespace std;
 7 
 8 class Solution {
 9 public:
10     vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
11         unordered_map<string, vector<string> > back_trace;
12         vector<unordered_set<string> > level(2);
13         
14         dict.insert(start);
15         dict.insert(end);
16         
17         int flag, nflag;
18         flag = 0;
19         nflag = !flag;
20         level[flag].insert(start);
21         
22         unordered_set<string>::iterator usit;
23         char ch, old_ch;
24         string word;
25         while (true) {
26             flag = !flag;
27             nflag = !nflag;
28             level[flag].clear();
29             for (usit = level[nflag].begin(); usit != level[nflag].end(); ++usit) {
30                 dict.erase(*usit);
31             }
32             for (usit = level[nflag].begin(); usit != level[nflag].end(); ++usit) {
33                 word = *usit;
34                 for (size_t i = 0; i < word.size(); ++i) {
35                     old_ch = word[i];
36                     for (ch = ‘a‘; ch <= ‘z‘; ++ch) {
37                         if (ch == old_ch) {
38                             continue;
39                         }
40                         word[i] = ch;
41                         if (dict.find(word) != dict.end()) {
42                             back_trace[word].push_back(*usit);
43                             level[flag].insert(word);
44                         }
45                     }
46                     word[i] = old_ch;
47                 }
48             }
49             if (level[flag].empty() || level[flag].count(end) > 0) {
50                 // found or not found
51                 break;
52             }
53         }
54         
55         single_result.clear();
56         for (size_t i = 0; i < result.size(); ++i) {
57             result[i].clear();
58         }
59         result.clear();
60         
61         if (!back_trace.empty()) {
62             recorverPath(back_trace, end);
63         }
64         
65         return result;
66     }
67 private:
68     vector<vector<string> > result;
69     vector<string> single_result;
70     
71     void recorverPath(unordered_map<string, vector<string> > &back_trace, string cur) {
72         if (back_trace.count(cur) == 0) {
73             // this word has no back trace, it is unreachable.
74             vector<string> single_path(single_result);
75             
76             single_path.push_back(cur);
77             reverse(single_path.begin(), single_path.end());
78             result.push_back(single_path);
79             return;
80         }
81         
82         const vector<string> &v = back_trace[cur];
83         vector<string>::const_iterator usit;
84         
85         single_result.push_back(cur);
86         for (usit = v.begin(); usit != v.end(); ++usit) {
87             recorverPath(back_trace, *usit);
88         }
89         single_result.pop_back();
90     }
91 };