Leetcode 127 **
2024-10-04 10:18:05
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordset(wordList.begin(),wordList.end());
wordset.erase(beginWord);
int res = ;
queue<string> que{{beginWord}};
while(!que.empty()){
int len = que.size();
for(int i=;i < len;i++){//坑:int i=0;i < que.size();i++ que.size()会不停改变
string word = que.front(); que.pop();
if(word == endWord) return res+;
for(int i=;i < word.size();i++){
string newword = word;
for(char ch = 'a';ch <= 'z';ch++){
newword[i] = ch;
if(wordset.count(newword)){
que.push(newword);
wordset.erase(newword);
}
}
}
}
res++;
}
return ; //没找到
}
};
好题!第一次见这题还是在一年前刚学算法的时候,今日硬着头皮分析了下去,前几天写的DFS T了,我都写了DFS居然没有想到这其实是一个求图的最短跳数的题:
单词之间能够变化可以抽象为两点之间有一条有向路径,BFS找到第一个点有向路径连接的所有点加入队列,然后对队列中的点再找图中剩下直连的点,最先到达终点的距离就是层数,直接返回。
还有要把层次遍历和BFS联系起来!都是用的队列,对每“批次”的队列遍历循环,两者本质是一样的。
最后注意 que.size()的坑,之前遇到过,还好看出来了。
最新文章
- 严重: Exception sending context initialized event to listener instance of class
- 在freemarker中,价格 怎么将¥100变成 ¥100.00
- DataTable 获取列名 DataTable批量更新至数据库
- C#位操作符
- 解决asp.net mvc中*.resx资源文件访问报错
- java怎么连接sql server,需要注意的几点
- BZOJ 1051 受欢迎的牛
- WINDOWS API 函数(超长,值得学习)
- node.js(五)字符串转换
- ubuntu12.04中如何设定中文输入法
- SpringMVC注解HelloWorld
- I2C通信基本原理及其实现
- 1013. Battle Over Cities 用dfs计算联通分量
- 洛谷P4590 [TJOI2018]游园会(状压dp LCS)
- A2D Framework - 看如何精简业务逻辑 - 缓存子系统
- js创建并下载文件
- 运行gulp项目报错:AssertionError: Task function must be specified。
- [区块链]POW 与POS
- 配置CenOS网络,并用Xshell链接。
- Flv的结构分析