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()的坑,之前遇到过,还好看出来了。

最新文章

  1. 严重: Exception sending context initialized event to listener instance of class
  2. 在freemarker中,价格 怎么将¥100变成 ¥100.00
  3. DataTable 获取列名 DataTable批量更新至数据库
  4. C#位操作符
  5. 解决asp.net mvc中*.resx资源文件访问报错
  6. java怎么连接sql server,需要注意的几点
  7. BZOJ 1051 受欢迎的牛
  8. WINDOWS API 函数(超长,值得学习)
  9. node.js(五)字符串转换
  10. ubuntu12.04中如何设定中文输入法
  11. SpringMVC注解HelloWorld
  12. I2C通信基本原理及其实现
  13. 1013. Battle Over Cities 用dfs计算联通分量
  14. 洛谷P4590 [TJOI2018]游园会(状压dp LCS)
  15. A2D Framework - 看如何精简业务逻辑 - 缓存子系统
  16. js创建并下载文件
  17. 运行gulp项目报错:AssertionError: Task function must be specified。
  18. [区块链]POW 与POS
  19. 配置CenOS网络,并用Xshell链接。
  20. Flv的结构分析

热门文章

  1. kubectl基础支持
  2. Python 爬虫入门3种方法
  3. commons-beanutils使用介绍
  4. animate.css –齐全的CSS3动画库--- 学习笔记
  5. webbench高并发测试
  6. yum节省安装时间
  7. maven 引入外部jar包的几种方式
  8. Java——文件及目录File操作
  9. async await 多线程
  10. TypeError: add() argument after * must be an iterable, not Settings的错误原因