Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, 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.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
[分析] 使用bfs思路解决:维护一个层级遍历队列,考察当前层的每个单词,通过修改一个字母得到的新单词若出现在dict中则将新单词添加到考察队列的下一层中,且将该新单词从dict中删除,以避免出现hot-dot-hot的死循环,一层遍历完后考察下一层。bfs保证第一次找到endWord肯定是最短路径,因为bfs是层次遍历,同一层每个单词到beginWord的变换距离是相等的。参考
http://www.cnblogs.com/TenosDoIt/p/3443512.html
public class Solution {
public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
if (beginWord == null || endWord == null || wordDict == null)
return -1;
LinkedList<String> queue = new LinkedList<String>();
queue.offer(beginWord);
int len = 0;
int currLevel = 0, nextLevel = 1;
int L = beginWord.length();
while (!queue.isEmpty()) {
if (currLevel == 0) {
currLevel = nextLevel;
nextLevel = 0;
len++;
}
char[] curr = queue.poll().toCharArray();
for (int i = 0; i < L; i++) {
char oldChar = curr[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == oldChar) continue;
curr[i] = c;
String newWord = new String(curr);
if (newWord.equals(endWord))
return len + 1;
else if (wordDict.contains(newWord)) {
nextLevel++;
queue.offer(newWord);
wordDict.remove(newWord);
}
}
curr[i] = oldChar;
}
currLevel--;
}
return 0;
}
}
分享到:
相关推荐
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
leetcode 答案解析 golang解答
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-helper-1.7.1
970. 强整数对数运算function powerfulIntegers(x: number, y: number, bound: number): numb
leetcode-tag-dynamic programming
然后进入到LeetCode-Spider目录中修改config.json,其中outputDir需要填写该工程的/docs/views文件夹路径 { "username": "aaa", "password": "bbb", "outputDir": "/Users/liuyao/Downloads/LeetCode-Blog-Test/docs...
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode-tag-Tree
leetcode-tag-Stack
leetcode-tag-array