127. Word Ladder (很重要！！！)

beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWordto endWord, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the word list

For example,

Given:

beginWord = ​​"hit"​​

endWord = ​​"cog"​​

wordList = ​​["hot","dot","dog","lot","log"]​​​​"hit" -> "hot" -> "dot" -> "dog" -> "cog"​​,

return its length ​​5​​.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

​​Subscribe​​ to see which companies asked this question

class Solution {
public:
  int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
    queue<string> Q;
    set<string>visited;
    Q.push(beginWord);
    visited.insert(beginWord);
    int cnt = 1;
    while (!Q.empty()){
      cnt++;
      int size = Q.size();
      while (size--){
        string front = Q.front();
        Q.pop();
        for (int i = 0; i < front.size(); i++){
          for (char ch = 'a'; ch <= 'z'; ch++){
            if (ch == front[i]) continue;
            string tmp = front;
            tmp[i] = ch;
            if (wordList.count(tmp) && !visited.count(tmp)){
              if (tmp == endWord) return cnt;
              Q.push(tmp);
              visited.insert(tmp);
            }
          }
        }
      }
    }
    return 0;
  }
};