[单向BFS][双向BFS]leetcode127：单词接龙(medium)_单词接龙 leetcode 双端bfs

题目：

题解：

思路1：单向 BFS 使用最小步数模型即可，参考 AcWing 845. 八数码；

---

思路2：双向 BFS 两端向中间扩展即可，参考AcWing 190. 字串变换；

代码如下：

class Solution {
public:
    int ladderLength(string start, string end, vector<string>& a) {
        unordered_map<string,int> dist;
        unordered_set<string> dict(a.begin(),a.end());
        // 终点不在字典中，那么无法到达终点，直接返回 0
        if(!dict.count(end))return 0;
        queue<string> q;
        // 将起点加入队列以及加入距离数组
        q.push(start),dist[start]=1;
        while(q.size())
        {
            auto t=q.front();q.pop();
            int distance=dist[t];
            // 枚举该字符串得所有扩展方式：先枚举被扩展的位置，再枚举被替换的字符
            for(int i=0,n=t.size();i<n;++i)
            {
                string copy=t;
                for(int j=0;j<26;++j)
                {
                    // 位置 i 上的字符没有被替换
                    if('a'+j==t[i])continue;
                    // 位置 i 上的字符替换为新字符 j
                    copy[i]='a'+j;
                    // 扩展到的状态到达终点，返回距离+1
                    if(copy==end)return distance+1;
                    // 新状态不在字典中或者该状态已经被访问过了，就直接进行跳过
                    if(!dict.count(copy)||dist.count(copy))continue;
                    // 当前状态到新状态的距离进行更新，并加入队列
                    dist[copy]=distance+1,q.push(copy);
                }
            }  
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
public:
    unordered_set<string> dict;
    // 双向 BFS
    int ladderLength(string start, string end, vector<string>& a) {
        // 存放所有单词的字典
        for(auto s:a)dict.insert(s);
        if(!dict.count(end))return 0;
        // ds 表示从起点到扩展到的点的距离，de 表示终点到扩展到点的距离
        unordered_map<string,int> ds,de;
        // qs 表示从起点开始搜，qe 表示从终点开始搜。需要建立两个方向的队列，用来存储状态
        queue<string> qs,qe;
        // 存储起始位置和起始距离
        qs.push(start),ds[start]=1;
        qe.push(end),de[end]=1;
        // 只要两个队列都不为空时，才能继续扩展。若其中一个为空，或者都为空，说明s e是一定不连通的，不存在交集；否则只要中间是连通的，就一定可以变过去。
        while(qs.size()&&qe.size())
        {
            int t;
            // 每次选择从状态数少的队列开始进行扩展，这样来降低时间复杂度。
            if(qs.size()<=qe.size())t=extend(qs,ds,de);
            else t=extend(qe,de,ds);
            if(t)return t;
        }
        return 0;
    }

    int extend(queue<string>& q,unordered_map<string,int>& ds,unordered_map<string,int>& de)
    {
        int span=q.size();
        // 每次扩展需要将当前队列中所有的点进行扩展，这样保证搜索最短路径
        while(span--)
        {
            auto t=q.front();q.pop();
            // 进行状态的扩展：先枚举被替换字符的位置，再枚举剩余 25 个字符，构成扩展到的新单词
            for(int i=0,n=t.size();i<n;++i)
            {
                string copy=t;
                for(int j=0;j<26;++j)
                {
                    // 相同字符，不用被替换
                    if('a'+j==t[i])continue;
                    // 替换为新字符 j
                    copy[i]='a'+j;
                    // 若扩展到的状态再队列 e 中表示两队列相遇了，距离为 start->t-copy->end
                    if(de.count(copy))return ds[t]+de[copy];
                    // 新状态不在字典中或者该状态已经被访问过了，就直接进行跳过
                    if(!dict.count(copy)||ds.count(copy))continue;
                    // 更新起点到新状态 copy 的距离，并加入队列
                    ds[copy]=ds[t]+1,q.push(copy);
                }
            }
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56