126. Word Ladder II

I built my solution on top of problem 127 "Word Ladder". I use a hash map to store the prior string set of current string. The key is current string and the value is the prior string set. The reason I use unordered_set for prior strings is to avoid duplicates. The basic idea is to find the shortest transformation sequence first and then build the sequences by the hash map.

1:  class Solution {  
2:  private:  
3:    unordered_map<string, unordered_set<string>> mp;  
4:    queue<string> q;  
5:    vector<vector<string>> res;  
6:    vector<string> path;  
7:    int dist;  
8:  public:  
9:    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {  
10:      dist = helper(start, end, dict);  
11:      if (dist) output(start, end);  
12:      return res;   
13:    }  
14:    int helper(string &start, string &end, unordered_set<string> &dict) {  
15:      dict.insert(start);  
16:      q.push(start);  
17:      path.push_back(end);  
18:      dist = 1;  
19:      while (!q.empty()) {  
20:        int n = q.size();  
21:        for (int i = 0; i < n; i++) {  
22:          dict.erase(q.front());  
23:          q.push(q.front());  
24:          q.pop();  
25:        }  
26:        for (int i = 0; i < n; i++) {  
27:          string word = q.front();  
28:          q.pop();  
29:          if (word == end) return dist;  
30:          addNeighbors(word, dict);  
31:        }  
32:        dist++;  
33:      }  
34:      return 0;  
35:    }  
36:    void addNeighbors(string word, unordered_set<string> &dict) {  
37:      string tmp = word;  
38:      for (int i = 0; i < word.size(); i++) {  
39:        char c = tmp[i];  
40:        for (int j = 0; j < 26; j++) {  
41:          tmp[i] = 'a' + j;  
42:          if (dict.count(tmp)) {  
43:            q.push(tmp);  
44:            mp[tmp].insert(word);  
45:          }  
46:        }  
47:        tmp[i] = c;  
48:      }  
49:    }  
50:    void output(string &start, string end) {  
51:      if (path.size() == dist) {  
52:        if (start == end) {  
53:          reverse(path.begin(), path.end());  
54:          res.push_back(path);  
55:          reverse(path.begin(), path.end());  
56:        }  
57:        return;  
58:      }  
59:      int n = mp[end].size();  
60:      for (auto it = mp[end].begin(); it != mp[end].end(); it++) {  
61:        string s = *it;  
62:        path.push_back(s);  
63:        output(start, s);  
64:        path.pop_back();  
65:      }  
66:    }  
67:  };