感觉今天的难度应该和昨天的难度换一下
这题的建图好麻烦
不过优化建图确实挺棒的
不看题解是真不知道
题目描述
给定两个单词(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寻找最短路
思路比较容易想
这题困难的地方就是建图
因为题目中说只有一个字母不一样才可以转换,所有朴素的做法就是遍历,找出相差一个字母的两个单词,然后使这两个单词相连,但是这种做法时间复杂度比较高,每个单词都要和其他单词进行比较,这个复杂度是N,每次比较需要一个字母一个字母的比较,这个复杂度是word.size,所以一个单词和其余单词比较的复杂度是O(Nword.size)
LeetCode给出的题解中是这样优化的:
比如hit这个单词可以创建三个节点——#it,h#t,hi#(显示不出来),hot也可以创建三个节点——#ot,h#t,ho#,这样hit和hot就可以通过h#t建立连接了,把虚拟节点也加入图中,这样相邻两个节点之间一定是只有一个字母不一样。这样就可以省去比较的过程。同时用哈希表可以方便表示
因为图中加入了三个虚拟节点,所以路径长度会多一半,而且第一个点也需要算进去所以最后返回 长度 / 2 + 1
图建好之后就是bfs的模板就可以了。
C++ 代码
class Solution {
public:
unordered_map<string, int> wordId; // 哈希表,建立字符串与数字之间的关系,方便图的存储
vector<vector<int>> edge; // 存储图
int nodeNum = 0; // 与字符串对应的数字
void addWord(string& word)
{
if(!wordId.count(word)) // 如果这个点不在哈希表中就加入到哈希表中
{
wordId[word] = nodeNum ++;
edge.emplace_back(); // 预先分配空间,emplace_back和push_back的作用差不多,都是向vector的末尾插入元素,是C++11新出来的,但是两者的实现不一样,这里的emplace_back不能替换为push_back,在这里push_back起不到emplace_back的作用
}
}
void addEdge(string& word) // 图的建立
{
addWord(word);
int id1 = wordId[word];
for(char& it : word)
{
char temp = it; // 先把当前字符存起来,方便以后的恢复
it = '*';
addWord(word); // 因为使用了&,所以word会随着it的改变而改变
int id2 = wordId[word];
edge[id1].push_back(id2); // 建立无向图
edge[id2].push_back(id1);
it = temp; // 恢复word
}
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
for(string& word : wordList)
addEdge(word); // 建立无向图
addEdge(beginWord);
if(!wordId.count(endWord)) // 如果字典中不存在endWord,那beginWord无法转换为endWord,直接返回0即可
return 0;
// 开始进行bfs
vector<int> dis(nodeNum, INT_MAX);
int beginId = wordId[beginWord], endId = wordId[endWord];
dis[beginId] = 0;
queue<int> que;
que.push(beginId); // 把开始元素加入到队列中
while(!que.empty())
{
auto x = que.front(); // 每次取出队头元素,用队头元素更新到其他点的距离
que.pop();
if(x == endId)
return dis[endId] / 2 + 1; // 因为图中插入的有类似于h*t这样的元素,所以开始点到结束点的距离增加了一半,并且开始的点的距离没有加入,所以最后返回的结果为距离的一半加1
for(int& it : edge[x])
{
if(dis[it] == INT_MAX) // 如果相邻点的距离为INT_MAX则说明该点未被遍历到,更新该点的距离,加入到队列中
{
dis[it] = dis[x] + 1;
que.push(it);
}
}
}
return 0;
}
};