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

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

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:Only one letter can be changed at a time.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.

 

参考了:https://www.jianshu.com/p/753bd585d57e

用 BFS 的思想做,注意用hasset而不用queue的理由。

class Solution {    public int ladderLength(String beginWord, String endWord, List
wordList) { //bfs if(beginWord == null || endWord == null){ return 0; } if(beginWord.length() != endWord.length()){ return 0; } Set
visited = new HashSet<>(); Set
wordSet = new HashSet<>(wordList); int dist = 1; visited.add(beginWord); while(!visited.contains(endWord)){ Set
temp = new HashSet<>(); for(String word : visited){ for(int i = 0; i

 

转载于:https://www.cnblogs.com/incrediblechangshuo/p/9065383.html

你可能感兴趣的文章
zoj 2412 dfs 求连通分量的个数
查看>>
Java设计模式
查看>>
一文读懂 AOP | 你想要的最全面 AOP 方法探讨
查看>>
Spring Cloud 微服务分布式链路跟踪 Sleuth 与 Zipkin
查看>>
ORM数据库框架 SQLite 常用数据库框架比较 MD
查看>>
华为OJ 名字美丽度
查看>>
微信公众号与APP微信第三方登录账号打通
查看>>
onchange()事件的应用
查看>>
Windows 下最佳的 C++ 开发的 IDE 是什么?
查看>>
软件工程师成长为架构师必备的十项技能
查看>>
python 异常
查看>>
百度账号注销
查看>>
mysql-This version of MySQL doesn’t yet support ‘LIMIT & IN/ALL/ANY/SOME 错误解决
查看>>
BIEE Demo(RPD创建 + 分析 +仪表盘 )
查看>>
Cocos2dx 3.0开发环境的搭建--Eclipse建立在Android工程
查看>>
基本概念复习
查看>>
重构第10天:提取方法(Extract Method)
查看>>
Android Fragment使用(四) Toolbar使用及Fragment中的Toolbar处理
查看>>
解决pycharm在ubuntu下搜狗输入法一直固定在左下角的问题
查看>>
多线程day01
查看>>