这是y总说的另外一种路径枚举方式，力扣里会超时，不过看看还是对bfs求最短路理解有些帮助的

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        //这种写法和上一种主要不同在于路径选择上，这种是枚举了wordList中所有合法路径，是从list里挑选的
        unordered_map<string, int> dist;
        queue<string> q;
        int n = wordList.size();

        dist[beginWord] = 0;
        q.push(beginWord);

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

            for(int i = 0; i < n; i ++) {
                auto r = wordList[i];
                if(!dist.count(r) && check(r, t)){
                    dist[r] = dist[t] + 1;
                    if(r == endWord) return dist[r] + 1;
                    q.push(r);
                } 
            } 
        }
        return 0;
    }

    bool check(string& s, string& t) {
        int cnt = 0;
        for(int i = 0; i < s.size(); i ++)
            if(s[i] != t[i]) cnt ++;
        return cnt == 1;
    }
};

菜鸡求助
请问建图复杂度为啥不是 n L 26* logn 呢
n个单词
长度为L
26种字母
在容量为n的set中查找每个单词：logn

如果判断写成if(s.count(t)&&d[t]==0)可能会造成1s的运行时间，原因时初始化时d[i]除了起点其他皆为0，没有运用到&&的短路效果，而反过来写初始时是很多情况不在单词集合里的，造成了第一个false后面不用判断，运行速度提升。。

现在代码会超时——

请问下,楼主对于bfs和dfs有常用剪支的技巧吗

方法有很多，比如A*、迭代加深等等。基本思想都是提早判断当前分支是否可行，如果不可行，则剪掉。

我想法是先把单词序列全部存入set中,然后每次加入队列时,删除这个单词。不过不知道为什么卡在最后几个测试例子上了。。

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        if( beginWord == endWord ) return 0;
        set< string > sum;
        for( auto x: wordList ) sum.insert( x );
        queue< pair< string, int > > q;
        int l = beginWord.length();
        int goal = 0;
        q.push( { beginWord, 1 } );
        while( !q.empty() )
        {
            pair< string, int > now = q.front();
            q.pop();
            if( now.first == endWord )
            {
                goal = now.second;
                break;
            }
            for( auto x: sum )  
            {
                if( !cmpdif( x, now.first, l ) ) continue;
                q.push( { x, now.second + 1 } );
                sum.erase( x );
            }
        }
        return goal;
    }
    bool cmpdif( string a, string b, int l )
    {
        int flag = 0;
        for( int i = 0; i < l; ++ i )
        {
            if( a[ i ] != b[ i ] )
            {
                if( flag ) return false;
                flag = 1;
            }
        }
        return true;
    }
};

for( auto x: sum )  
{
    if( !cmpdif( x, now.first, l ) ) continue;
    q.push( { x, now.second + 1 } );
    sum.erase( x );
}

问题出在这里，迭代时删除元素会发生未知错误。
可以开个vector<string>先将所有要删除的元素保存起来，之后统一删除。改完之后即可Accept，如下所示：

vector<string> to_erases;
for ( auto x: sum )
{
    if( !cmpdif( x, now.first, l ) ) continue;
    q.push( { x, now.second + 1 } );
    to_erases.push_back(x);
}
for (auto x : to_erases) sum.erase(x);

看到别人速度更快的submission好多是用了unordered_set[HTML_REMOVED]，那种解法我完全不能理解诶。大佬能解释一下吗？
比如这种
class Solution{
public:
int ladderLength(string beginWord, string endWord, vector[HTML_REMOVED]& wordList){
unordered_set[HTML_REMOVED] s(wordList.begin(), wordList.end());
if(s.find(endWord) == s.end())
return 0;

    unordered_set<string> hd({beginWord}), tl({endWord});
    int cnt = 2;

    while(!hd.empty() && !tl.empty()){
        if(hd.size() > tl.size())
            swap(hd, tl);

        unordered_set<string> tm;
        for(auto w : hd){
            for(int i = 0; i < w.size(); ++i){
                auto c = w[i];
                for(int j = 0; j < 26; ++j){
                    if(j + 'a' == c) continue;
                    w[i] = j + 'a';
                    if(tl.count(w))
                        return cnt;
                    if(s.count(w)){
                        tm.insert(w);
                        s.erase(w);
                    }
                }
                w[i] = c;
            }
        }
        cnt++;
        swap(hd, tm);
    }
    return 0;
}

};

unordered_set和unordered_map都是可以的，这不是关键。
关键是枚举下一个相邻点时，上面的题解是直接枚举其它所有单词，再判断是否只有一个字母相同，复杂度是 $O(nL)$；而这种比较快的方式是枚举当前单词的每个位置，然后用a到z依次替换，然后再判断修改后的单词是否存在，计算量是 $26 * L^2$，当 $n$ 比较大时会快很多。

赞~

这个solution是双向bfs吧，能给下原贴链接吗？

我刚发现这个solution除了枚举边的方式不同之外，还利用了双向BFS。
别人的代码可以在leetcode的提交记录的柱状图里看，点一下排名靠前的柱子就会弹出代码。

这个代码用右下角私信发你了

当词典规模比较大, 假如遍历每个位置所有可能的修改, 好像时间短一点, 这样的话时间复杂度好像是O(26 * max(word.length()) * n) ?

没错！当 $n$ 比较大的时候，遍历每个单词每个位置所有可能的修改会快很多。
假如单词长度是 $L$，总单词个数是 $n$，那么对于每个单词枚举每个位置的所有可能，一共是 $26 \times L \times n$ 次，每次去哈希表中查找修改后的单词是否存在，还需要 $O(L)$ 的计算量，所以总时间复杂度是 $O(26 L^2n) = O(L^2n)$。

难怪！！！我是想着dfs+哈希 过了二十多个测试样例 后面单词很短但词典很多的时候就TLE了。。。

这道题dfs效率会低一些。因为bfs第一次收到的路径一定是最短的，但dfs没有这个性质。

恩恩！是的 没有深入思考问题的本质 直接下意识就dfs了。
一般类似最短路思想的问题bfs效果大都是比dfs好的哈hhh

yls,哈希表判断一个单词是否存在不是O(1)的复杂度吗？那在每次枚举中其实就是枚举长度L，然后枚举26个字母，另外一共是n个node，所以就是$O(26nL)$的呀，为什么是$O(26nL^2)$

哈希一个字符串的计算量是和字符串长度成正比的。