力扣127题单词接龙,bfs_力扣 127,单词接龙 python

127. 单词接龙

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

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

说明:

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

示例 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” 不在字典中，所以无法进行转换。

思路:
难点在于如何将图建立起来,我们可以用哈希表吧字典中每个单词存起来,方便查找,每两个单词只要有一个字母不一样就是相连.我们可以拿一个单词举例,hit 一共三个字母,我们可以枚举每个字母,吧h换成’a’~‘z’ ait bit…然后在哈希表里寻找是否存在,存在的话说明是这两个单词是相连的,然后换i,t等等.
预先工作:
吧字典存储在哈希表中,判断一下,哈希表里面有没有endword.
然后准备一个队列用来广搜,准备一个哈希表map(string,bool) ,用来判断某个但是是否被访问过
然后开始广搜,当队列不为空循环继续,第一步得到当前队列的大小,这个代表这一层的单词个数,然后遍历每个单词,遍历的时候,使用上述的方法,吧和这个单词相连的且没有被访问过的,添加到队列中,如果相同的单词就是目标单词,直接返回当前step+1.遍历结束了,说明这一层弄好了,step+1;
最后返回step.

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_set>
#include<queue>
#include<unordered_map>
using namespace std;


class Solution {
public:
	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
		//哈希表,方便查找
		unordered_set<string> set;
		for (int i = 0; i < wordList.size(); i++)
		{
			set.insert(wordList[i]);
		}
		if (wordList.size() == 0 || set.find(endWord) == set.end())
		{
			return 0;
		}
		//准备一个队列用来广搜
		queue<string> q;
		q.push(beginWord);
		int step = 1;
		//visited 的哈希表key是string value是bool表示是否被访问过
		unordered_map<string, bool> map(wordList.size()+1);
		for (int i = 0; i < wordList.size(); i++)
		{
			map[wordList[i]] = false;
		}
		map[beginWord] = true;
		int wordLen = beginWord.size();
		while (!q.empty())
		{
			//获取当前这层单词的个数
			int current_size = q.size();
			for (int i = 0; i < current_size; i++){
				//开始遍历
				string word = q.front(); q.pop();
				
				for (int j = 0; j < wordLen; j++)
				{//寻找相连的单词的过程
					char origin = word[j];
					for (char c = 'a'; c <= 'z'; c++)
					{
						if (c == word[j]) continue;
						word[j] = c;
						//找到了
						if (set.find(word) != set.end()){
							if (!map[word]){
								//且没背访问过添加到队列中
								if (word != endWord){
									q.push(word);
									map[word] = true;
								}
								else {
									//如果是目标单词,返回结果
									return step + 1;
								}
							}
						}
					}
					//修改过的一个字母,还原
					word[j] = origin;
				}
			}
			//遍历完了一个层,步数+1
			step++;
		}
	}
};

int main()
{
	string beginWord = "hit";
	string endWord = "cog";
	vector<string> a;
	a.push_back("hot");
	a.push_back("dot");
	a.push_back("dog");
	a.push_back("lot");
	a.push_back("log");
	a.push_back("cog");
	Solution s;
	cout<<s.ladderLength(beginWord, endWord, a);
}
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89