LeetCode 127. 单词接龙（图的BFS/双向BFS）_leetcode 单词接龙 127 bfs

1. 题目

给定两个单词（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" 不在字典中，所以无法进行转换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-ladder
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 图的BFS解题

题目有点恶心的地方在于，beginWord不知道是不是在list内，需要判断
类似题目：
程序员面试金典 - 面试题 17.22. 单词转换（BFS）
LeetCode 126. 单词接龙 II（图的BFS）

2.1 单向BFS

• 利用队列进行BFS

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int len = wordList.size(), i, k, n, lv = 0;
        unordered_map<string,int> m;
        bool visited[len] = {false};
        for(i = 0; i < len; ++i)
        {
            m[wordList[i]] = i;
            if(wordList[i] == beginWord)
                visited[i] = true;
        }
        if(m.find(endWord) == m.end())
        	return 0;
        queue<string> q;
        string str;
        q.push(beginWord);
        while(!q.empty())
        {
        	lv++;
        	n = q.size();
        	while(n--)
        	{
	        	for(i = 0; i < beginWord.size(); ++i)
	        	{//对每个单词的每个字符进行改变
                    str = q.front();
                    for(k = 1; k <= 25; ++k)
                    {
    	        		str[i] += 1;
    	        		if(str[i] > 'z')
    	        			str[i] = 'a';
    	        		if(m.find(str) != m.end() && !visited[m[str]])
    	        		{	//在集合中，且没有访问的
    	        			q.push(str);
    	        			visited[m[str]] = true;
    	        			if(str == endWord)
            					return lv+1;
    	        		}
                    }
	        	}
	        	q.pop();
	        }
        }
        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

2.2 双向BFS ！厉害了

• 从起始和终点分别开始BFS，2个队列
• visited 存储int值，初始化为0，正向访问了+1，反向访问了+2，如果某个visited的值为3，说明都访问到了（连通了）
• 每次选择队列较短的一端继续BFS（减少队列扩大的规模，提高效率）

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int len = wordList.size(), wlen = beginWord.size(), i, k, n, n1, n2, flag, lv = 0;
        unordered_map<string,int> m;
        vector<int> visited(len,0);
        bool beginWordInList = false;
        for(i = 0; i < len; ++i)
        {
            m[wordList[i]] = i;
            if(wordList[i] == beginWord)//判断beginWord在List中否
            {
                visited[i] = 1;//beginWord正向访问
                beginWordInList = true;
            }
        }
        if(!beginWordInList)//beginWord不在list中
        {
            visited.push_back(1);//添加起点正向访问，值为1
            m[beginWord] = len;//哈希表添加
        }
        if(m.find(endWord) == m.end())
            return 0;
        queue<string> q1, q2;
        string str;
        q1.push(beginWord);
        q2.push(endWord);
        visited[m[endWord]] = 2;//终点反向访问了，值为2
        while(!q1.empty() && !q2.empty())
        {
            lv++;//走的步数
            n1 = q1.size();
            n2 = q2.size();
            queue<string> &Q = n1<n2 ? q1 : q2;//Q是较短的队列的引用
            flag = n1<n2 ? 1 : 2;//访问后增加的值
            n = Q.size();
            while(n--)
            {
                for(i = 0; i < wlen; ++i)
                {
                    str = Q.front();
                    for(k = 1; k <= 25; ++k)
                    {
                        str[i] += 1;
                        if(str[i] > 'z')
                            str[i] = 'a';
                        if(m.find(str) != m.end() && visited[m[str]] != flag)
                        {	//不等于1说明正向没有访问，不等于2说明反向没有访问
                            Q.push(str);
                            visited[m[str]] += flag;
                            if(visited[m[str]] == 3)//等于3说明，双向访问过，找到路径
                                return lv+1;
                        }
                    }
                }
                Q.pop();
            }
        }
        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