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:

Only one letter can be changed at a time Each intermediate word must exist in the word list For example,

Given: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        wordList.insert(endWord);

        queue<string> nextVisit;
        getNextWord(beginWord, nextVisit, wordList);

        int dis = 2;

        while(!nextVisit.empty()){
            int num = nextVisit.size();

            //注意此处使用了队列的初始大小来遍历这一层(数量为num)
            for(int i = 0; i < num; i++){
                string word = nextVisit.front();
                nextVisit.pop();

                if(word == endWord) return dis;
                getNextWord(word, nextVisit, wordList);
            }
            dis++;
        }
        return 0;
    }
private:
    void getNextWord(string &word, queue<string> &nextWord, unordered_set<string> &wordList){

        for(int i = 0; i < word.size(); i++){
            auto c = word[i];
            for(int j = 0; j < 26; j ++){
                word[i] = 'a' + j;
                if(wordList.find(word) != wordList.end()){
                    wordList.erase(word);
                    nextWord.push(word);
                }
            }
            word[i] = c;
        }
    }
};

使用从两边开始找的BFS，每次都找长度短的来遍历

class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        unordered_set<string> head, tail, *phead, *ptail;

        head.insert(beginWord);
        tail.insert(endWord);
        int dis = 2;

        while(!head.empty() && !tail.empty()){
            if(head.size() < tail.size()){
                phead = &head;
                ptail = &tail;
            }else{
                phead = &tail;
                ptail = &head;
            }

            //遍历这一层次中所有单词的相邻单词，temp存储的是下一层所有的单词
            unordered_set<string> temp;
            for(auto iter = phead->begin();iter != phead->end(); iter++){
                string word = *iter;
                wordList.erase(word);

                //遍历这一层中的某个节点的相邻单词，是否是终止单词或者在词典中
                for(int i = 0; i < (int)word.size(); i++){
                    char c = word[i];
                    for(int j = 0; j < 26; j++){
                        word[i] = 'a' + j;

                        if(ptail->find(word) != ptail->end()){
                            return dis;
                        }

                        if(wordList.find(word) != wordList.end()){
                            wordList.erase(word);
                            temp.insert(word);
                        }
                    }
                    word[i] = c;
                }
            }

            dis++;
            swap(*phead, temp);
        }
        return 0;
    }
};