Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog"
,
return its length 5
.
题目地址:https://oj.leetcode.com/problems/word-ladder/
采用BFS遍历,分别遍历start单词中的每个字母,找出只替换一个字母,在dict中出现的单词,将其放入队列。然后再依次遍历队列中的值。
public static int ladderLength(String start, String end, HashSet<String> dict) { int count = 1; Queue<String> queue = new LinkedList<String>(); Set<String> set = new HashSet<String>(); queue.add(start); int distance = 1; while (count > 0) { while (count > 0) { char chars[] = queue.poll().toCharArray(); for (int i = 0; i < chars.length; i++) { char temp = chars[i]; for (char c = 'a'; c <= 'z'; c++) { if (c == temp) continue; chars[i] = c; String str = new String(chars); if (str.equals(end)) return distance + 1; if (dict.contains(str) && !set.contains(str)) { set.add(str); queue.add(str); } } chars[i] = temp; } count--; } count = queue.size(); distance++; } return 0; }
相关推荐
126.Word_Ladder_II_词语阶梯二【LeetCode单题讲解系列】
经典字梯游戏c++代码,经测试通过的哦,leetcode上面的题目
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
大佬的leetcode刷题笔记(c++版本)
vs code LeetCode 插件
leetcode中文版
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
自己做leecode题目的总结,做个分享从事服务端开发,少不了要接触网络编程。epoll作为linux下高性能网络服务器的必备技术至关重要,nginx、redis、skynet和大部分游戏服务器都使用到这一多路复用技术。...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
leetcode高频面试笔试题150+道,亲身总结。
LeetCode面试笔试题
LeetCode 刷题笔记
(C++)LeetCode刷题题解答案