数据结构算法--单词接龙(C++)
程序员文章站
2022-04-15 23:39:03
127. 单词接龙 - 力扣(LeetCode)要找最短的,直接bfs,bfs找到的肯定是最短的。抽象在一个无向无权图中,每个单词作为节点,差距只有一个字母的两个单词之间连一条边。问题变成找到从起点到终点的最短路径,如果存在的话。因此可以使用广度优先搜索方法。相当于每条边权值均为1的有向图,如果起始单词改变一个字母可以变为另一个单词,那么这两个单词之间的距离为1,否则为无穷。怎么确定一个单词改变一个字母是不是能成为另一个单词呢?可以遍历两个单词进行统计,但是如果单词表太大的话,速度会很慢。由于只...
要找最短的,直接bfs,bfs找到的肯定是最短的。
抽象在一个无向无权图中,每个单词作为节点,差距只有一个字母的两个单词之间连一条边。问题变成找到从起点到终点的最短路径,如果存在的话。因此可以使用广度优先搜索方法。
相当于每条边权值均为1的有向图,如果起始单词改变一个字母可以变为另一个单词,那么这两个单词之间的距离为1,否则为无穷。
怎么确定一个单词改变一个字母是不是能成为另一个单词呢?可以遍历两个单词进行统计,但是如果单词表太大的话,速度会很慢。
由于只有小写字母,可以使用遍历字母的方法,一次性检查所有的单词,具体减代码;
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> s(wordList.begin(), wordList.end());
queue<pair<string, int>> q;
q.push({beginWord, 1});//第一个元素是字符串,第二个是该字符串到beginword的序列长度
while(!q.empty()){
string tmp = q.front().first;
int step = q.front().second;
q.pop();
if(tmp == endWord) return step;//走到了终点
for(int i = 0; i < tmp.size(); ++i){
char ch = tmp[i];
//遍历字母来寻找距离为1(只用改变一个字母)的单词
for(char c = 'a'; c <= 'z'; ++c){
if(ch == c) continue;
tmp[i] = c;//替换单个字符
if(s.count(tmp)){
q.push({tmp, 1+step});
s.erase(tmp);//该节点使用过了,可以删除
}
}
tmp[i] = ch;//复原
}
}
return 0;
}
};
其中查找的部分,其实还可以使用字典树实现。
本文地址:https://blog.csdn.net/qq_32523711/article/details/108239342