博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
127. Word Ladder
阅读量:6958 次
发布时间:2019-06-27

本文共 2295 字,大约阅读时间需要 7 分钟。

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:beginWord = "hit",endWord = "cog",wordList = ["hot","dot","dog","lot","log","cog"]Output: 5Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",return its length 5.

Example 2:

Input:beginWord = "hit"endWord = "cog"wordList = ["hot","dot","dog","lot","log"]Output: 0Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

关键字 "...find the length of shortest transformation sequence from beginWord to endWord..." 最短路径,用BFS解决:1.需要Queue来做BFS,2.hash table来避免重复。 BFS:起点是beginWord,边是变换成和当前word只差一个字母并且存在在字典里的词。 这道题要求出最短路径是多少(多少层),当用BFS遍历时,需要明确知道什么时候当前层结束,开始下一层,层数此时+1。最简单的做法是用两个queue来实现:queue1装当前层的节点,queue2装下一层节点,当queue1为空时,代表当前层节点遍历结束.
1 class Solution { 2 public: 3     int ladderLength(string beginWord, string endWord, vector
& wordList) { 4 unordered_set
dict(wordList.begin(),wordList.end()); //hashtable containing unvisited words 5 int length = 1; 6 queue
queue1; //current level 7 queue
queue2; //next level 8 queue1.push(beginWord); 9 10 //BFS11 while(!queue1.empty()){12 string currWord = queue1.front();13 if(currWord==endWord){ //equals endWord: find the transformation14 return length;15 }16 queue1.pop();17 18 //checking neighbors19 //1. each letter can be changed20 for(int i=0;i
temp;44 queue2 = temp;45 }46 }47 48 return 0;49 }50 };

 

转载于:https://www.cnblogs.com/ruisha/p/9219015.html

你可能感兴趣的文章
C语言中 struct成员变量顺序对内存的占用
查看>>
POJ1291-并查集/dfs
查看>>
移动办公首选!电商热卖轻薄本高低该怎么选?
查看>>
[译] RNN 循环神经网络系列 1:基本 RNN 与 CHAR-RNN
查看>>
Android技能树 — PopupWindow小结
查看>>
如何在create-react-app项目中使用vw实现手淘vw移动端适配布局
查看>>
Wormhole燃烧地址到底有多安全
查看>>
Web探索之旅 | 第三部分第三课:协议
查看>>
20个优秀手机界面扁平化设计,让你一秒看懂扁平化
查看>>
从百度的PPT文化看程序员晋升
查看>>
Python测试登录功能
查看>>
babel插件入门-AST(抽象语法树)
查看>>
ubuntu 16.04下docker的安装
查看>>
web页面渲染(一)
查看>>
roadhog+dva中环境变量的配置
查看>>
js解决0.1+0.2==0.3的问题的几种方法
查看>>
python中#!/usr/bin/python与#!/usr/bin/env python的区别
查看>>
第10章:并发和分布式编程 10.1并发性和线程安全性
查看>>
多线程之死锁就是这么简单
查看>>
Python字符串格式化
查看>>