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:  };  

127. Word Ladder

You can image the wordList as a forest from the beginning word. Each word with one character difference from the beginning word becomes its child. Note, to avoid loop, we need to erase/tag the visited child from the wordList. After constructing this, we move down to traverse its children. And the same rule, i.e. each word with one character difference become the child. We can keep doing that until we find the ending word or we find nothing.

1:  class Solution {  
2:  public:  
3:    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {  
4:      wordList.insert(endWord);  
5:      queue<string> visit;  
6:      addNeighbors(beginWord, wordList, visit);  
7:      int distance = 2;  
8:      while (!visit.empty()) {  
9:        int n = visit.size();  
10:        for (int i = 0; i < n; i++) {  
11:          string word = visit.front();  
12:          visit.pop();  
13:          if (word == endWord) return distance;  
14:          addNeighbors(word, wordList, visit);  
15:        }  
16:        distance++;  
17:      }  
18:      return 0;  
19:    }  
20:    void addNeighbors(string word, unordered_set<string>& wordList, queue<string> &visit) {  
21:      wordList.erase(word);  
22:      for (int i = 0; i < word.size(); i++) {  
23:        char c = word[i];  
24:        for (int j = 0; j < 26; j++) {  
25:          word[i] = 'a'+j;  
26:          if (wordList.find(word) != wordList.end()) {  
27:            visit.push(word);  
28:            wordList.erase(word);  
29:          }  
30:        }  
31:        word[i] = c;  
32:      }  
33:    }  
34:  };