Leetcode 127. 单词接龙 BFS_leetcode 单词接龙 127 bfs

127. 单词接龙给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:

如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:

输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]

输出: 5

解释: 一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
返回它的长度 5。
示例 2:

输入:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,“dot”,“dog”,“lot”,“log”]

输出: 0

解释: endWord “cog” 不在字典中，所以无法进行转换。

方法一：不用邻接表，直接bfs循环过程中计算

class Solution{
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList){
        //加入所有节点，访问过一次，删除一个。
        unordered_set<string> s;
        for (auto &i : wordList) s.insert(i);

        queue<pair<string, int>> q;
        //加入beginword
        q.push({beginWord, 1});

        string tmp; //每个节点的字符
        int step;    //抵达该节点的step

        while ( !q.empty() ){
            if ( q.front().first == endWord){
                return (q.front().second);
            }
            tmp = q.front().first;
            step = q.front().second;
            q.pop();

            //寻找下一个单词了
            char ch;
            for (int i = 0; i < tmp.length(); i++){
                ch = tmp[i];
                for (char c = 'a'; c <= 'z'; c++){
                    //从'a'-'z'尝试一次
                    if ( ch == c) continue;
                    tmp[i] = c ;
                    //如果找到的到
                    if (  s.find(tmp) != s.end() ){
                        q.push({tmp, step+1});
                        s.erase(tmp) ; //删除该节点
                    }
                tmp[i] = ch; //复原
                }
               
            }
        }
        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

方法二：邻接表+双向bfs

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) 
    {
        if (beginWord == endWord) return 1;
        bool flag = true;

        map<string, vector<string>> comboList;
        for (auto w : wordList)
        {
            if (w == endWord)
            {
                flag = false;
            }
            for (size_t i = 0; i < w.size(); i++)
            {
                auto temp = w;
                temp[i] = '*';
                comboList[temp].push_back(w);  // 每个string放入它对应的*式子里
            }
        }
        if (flag) return 0;

        unordered_map<string, int> vi[2];
        queue<string> que[2];
        que[0].push(beginWord);
        vi[0][beginWord] = 1;
        que[1].push(endWord);
        vi[1][endWord] = 1;

        while (!que[0].empty() || !que[1].empty())
        {
            int k = (que[0].size() < que[1].size()) ? 0 : 1;  //选择短的那个队列遍历
            k = (que[k].size() == 0) ? (k + 1) % 2 : k;  //短的长度是0，选长的那个
            
            for (int i = que[k].size(); i > 0; i--)
            {
                auto q = que[k].front();  //出队
                que[k].pop();

                for (size_t i = 0; i < q.size(); i++)
                {
                    auto temp = q;
                    temp[i] = '*';  //换成他的范式，找其他相同范式不同的字符串，即下一个接龙

                    for (auto w : comboList[temp])
                    {
                        if (vi[k].count(w) != 0) continue;
                        int k2 = (k + 1) % 2;
                        if (vi[k2].count(w) != 0)   //两个队列可以访问到同一个字符串，相接，返回
                        {
                            return vi[k2][w] + vi[k][q];
                        }

                        que[k].push(w);            //放入队列
                        vi[k][w] = vi[k][q] + 1;    //层数
                    }
                }
            }
        }
        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
57
58
59
60
61
62
63