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