LeetCode 127.单词接龙 （BFS的妙用）

做LC的daily这题非常有意思。

题目大意：给你一个开始word一个结尾word和一个wordlist,问你是否可以从开始变形到结尾（图的起点到终点），一次只能变一个字母，如果可以的话输出最小变形次数（最短路径）。
如：

string beginWord = "hit";
string endWord = "cog";
vector<string> wordList = { "hot", "dot", "dog", "lot", "log", "cog" };
1
2
3

由于BFS是一层一层扫描的，所以第一次扫描到终点节点时的深度，就是终点的最短路径了。
以下是解法：

class Solution {
public:
	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
		unordered_set<string> wordSet(wordList.begin(), wordList.end()); //提高查找效率
		if (wordSet.find(endWord) == wordSet.end())//endword不在set中，直接返回0
			return 0;

		unordered_map<string, int> viewed; //访问过的节点标记
		queue<string> Q;  //BFS用的队列
		Q.push(beginWord);

		//访问过了起点，初始化viewed
		viewed.insert(pair<string, int>(beginWord, 1));
		
		while (!Q.empty()) //开始BFS
		{
			string word = Q.front();
			Q.pop();
			int path = viewed[word];  //当前访问到节点的路径（由于BFS，所以一次大循环深一层）
			for (int i = 0; i < word.length(); i++) //三个字母的替换
			{
				string tmp = word;  //新的临时生成的word
				for (int j = 0; j < 26; j++) 
				{
					tmp[i] = j + 'a';  //26个字母一个一个去替换

					if (tmp == endWord)
						return path + 1;   //如果直接等于结果了，path+1即可

					if (wordSet.find(tmp) != wordSet.end() && viewed.find(tmp) == viewed.end()) //有路且未访问
					{
						Q.push(tmp); //入队
						viewed.insert(pair<string, int>(tmp, path + 1));//添加访问信息，path深了一层
					}
				}
			}
		}
		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

有几点非常巧妙：
1.这题用到了图的BFS概念，但实际上并没有真的创建一个G矩阵或者邻接表之类的。
2.unordered_set底层是哈希表，所以查找效率非常高，用来代替vector.find()。后者应该是基于二分查找（？？？ 暂不确定）
3.unordered_map用来标记viewed。和模板题不同的是，模板只能表示是否有访问，而这种写法可以同时表示是否有访问，以及当前深度是多少。
4.题解中使用的是暴力替换字母，这里还有优化空间。
5.官方题解中还提到了使用双向BFS。