[数据结构与算法]leetcode127.单词接龙C++

链接：

https://leetcode-cn.com/problems/word-ladder/

描述：

示例：

代码：

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        //hash用于查询变化后的时候在给定字典中。
        unordered_set<string> wordDirt(wordList.begin(),wordList.end());

        //标记单词是否被访问
        unordered_set<string> visted;
        visted.insert(beginWord);

        //初始化队列
        queue<string> q;
        q.push(beginWord);
        int res = 1;

        while(!q.empty())
        {
            //新插入队列的长度
            int nextsize = q.size();

            while(nextsize--)
            {
                string curWord =q.front();
                q.pop();
                //尝试替换当前位置的每一个位置
                for(int i = 0;i<curWord.size();i++)
                {
                    string newWord = curWord;
                    //每一个位置用26个字母进行替换，然后用hash查找是否在给定字典里面
                    for(auto ch = 'a';ch<='z';ch++)
                    {
                        newWord[i] = ch;
                        //给定字典里面是否有这个单词
                        if(!wordDirt.count(newWord) || visted.count(newWord)) continue;
                        //找到结果
                        if(newWord == endWord) return res+1;
                        //没有成功，新单词入队列
                        visted.insert(newWord);
                        q.push(newWord);
                    }
                }
            }
            res++;
        }
        //转换不成功
        return 0;
    }
};