LeetCode 127. 单词接龙

LeetCode 127. 单词接龙
思路：

建图，每一个单词都是一个点，由于边权是1，所以可以使用bfs进行搜索。

代码：

class Solution {
public:
    vector<string> q;
    unordered_set<string> S;//存的是wordlist中所有的字符串
    unordered_map<string,int> dist;//到起点的距离

    string beginWord;
    int ladderLength(string _beginWord, string endWord, vector<string>& wordList) {
        for(auto word : wordList) S.insert(word);
        beginWord = _beginWord;
        dist[beginWord] = 0;
        queue<string> q;
        q.push(beginWord);

        while(q.size()){
            auto t = q.front();
            q.pop();

            string r = t;

            for(int i=0;i<t.size();i++){
                t = r;
                for(char j = 'a';j <= 'z';j++){
                    t[i] = j;
                    if(S.count(t) && dist.count(t) == 0){
                        dist[t] = dist[r] + 1;
                        //最短转换序列 中的 单词数目 返回的不是边数
                        if(t == endWord) return dist[t] + 1;
                        
                        q.push(t);
                    }
                }
            }
        }
        return 0;
    }
};