solution.cpp

//Dijkstra算法的思路
class Solution
{
public:
    int ladderLength(string beginWord, string endWord, vector<string> &wordList)
    {
        unordered_set<string> set(wordList.begin(), wordList.end());
        if (!set.count(endWord))
            return 0;
        queue<pair<string, int>> q; //<字符串，该字符串到beginword的距离>
        q.push({beginWord, 1});
        while (!q.empty())
        {
            string cur = q.front().first;
            int step = q.front().second;
            q.pop();
            if (cur == endWord)
                return step;

            for (int i = 0; i < cur.size(); ++i)
            {
                char ch = cur[i];
                //遍历字母来寻找距离为1（只用改变一个字母）的单词，也即可达的单词
                for (char c = 'a'; c <= 'z'; ++c)
                {
                    if (c == ch)
                        continue;
                    cur[i] = c; //替换单个字符
                    if (set.count(cur))
                    {
                        q.push({cur, 1 + step});
                        set.erase(cur); //该节点使用过了，需要进行删除
                    }
                }
                cur[i] = ch; //复原
            }
        }
        return 0;
    }
};