127. Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord="hit"
endWord="cog"
wordList=["hot","dot","dog","lot","log","cog"]

As one shortest transformation is"hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

S: BFS

BFS关键点：

1. queue存储访问顺序
2. 记录访问过的点，此题是通过删除word dict中访问过的元素来达到
3. 用queue当前的size判断本层元素个数

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict;
        for (string s : wordList) {
            dict.insert(s);
        }
        int result = 2;
        int size = beginWord.size();
        queue<string> words;
        words.push(beginWord);
        while (!words.empty() && !dict.empty()) {
            int n = words.size();
            for (int i = 0; i < n; ++i) {
                string word = words.front();
                words.pop();
                for (int j = 0; j < size; ++j) {
                    for (int k = 0; k < 26; ++k) {
                        if (word[j] != 'a' + k) {
                            string newWord = word;
                            newWord[j] = 'a' + k;
                            if (dict.find(newWord) != dict.end()) {
                                if (newWord == endWord) {
                                    return result;
                                }
                                words.push(newWord);
                                dict.erase(newWord);
                            }
                        }
                    }
                }
            }
            result++;
        }
        return 0;
    }