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
.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
Solution:
Breadth First Search.
起个好的变量名多么的重要啊。我看到网上写的好多代码,那变量名起的太有混淆的反作用了。
- 和当前单词相邻的单词是:对当前单词改变一个字母且在字典中存在的单词
- 找到一个单词的相邻单词,加入bfs队列后,要从字典中删除,因为不删除的话会造成类似于hog->hot->hog的死循环。而删除对求最短路径没有影响,因为我们第一次找到该单词肯定是最短路径,即使后面其他单词也可能转化得到它,路径肯定不会比当前的路径短(如果要输出所有最短路径,则不能立即从字典中删除)
- bfs队列中用width==0来标识层与层的间隔,每次碰到width==0,遍历深度+1
这个算法中最坏情况是把所有长度为L的字符串都看一下,或者把字典中的字符串都看一下,而长度为L的字符串总共有26^L,所以时间复杂度是O(min(26^L, size(dict)),空间上需要存储访问情况,也是O(min(26^L, size(dict))。
public int ladderLength(String start, String end, HashSet<String> dict) { if (dict == null || dict.size() == 0) return 0; Queue<String> queue = new LinkedList<String>(); queue.offer(start); dict.remove(start); int depth = 1; // ladder的深度 int width = 1; // 层的宽度,即每一层变换的单词的总数量 while(!queue.isEmpty()) { char[] str = queue.poll().toCharArray(); for (int i=0; i < str.length; i++) { for (char c = 'a'; c <= 'z'; c++) { if(str[i] == c) continue; char tmp = str[i]; str[i] = c; String word = new String(str); if (word.equals(end)) return depth + 1; if (dict.remove(word)){ //当该单词在词典中,删除并返回true;若不存在该单词则返回false queue.offer(word); } str[i] = tmp; } } if(--width == 0) { width = queue.size(); //更新为下一层变换的单词的数量 depth++; } } return 0; }
C++的代码:
int ladderLength(string start, string end, unordered_set<string> &dict) { queue<string> q; q.push(start); dict.erase(start); int len = 1; while(!q.empty()) { int size = q.size(); for(int i=0; i<size; i++) { string s = q.front(); q.pop(); for(int j=0; j<s.size(); j++) { char ch = s[j]; for(char c='a'; c<='z'; c++) { if(c == ch) continue; s[j] = c; if(s == end) return len+1; if(dict.count(s)) { q.push(s); dict.erase(s); } } s[j] = ch; } } len++; } return 0; }
相关推荐
大佬的leetcode刷题笔记(c++版本)
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
LeetCode题解 - Java语言实现-181页.pdf
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
彩色版本 正版 pdf 精讲数据结构 + 算法 链表 树 图表 贪心算法 指针 动态规划 查找算法
leetcode1-300.docx
leetcode 答案leetcode--python Leetcode 的答案
500195422331430LeetCode题解 - Java语言实现.zip
leetcode 答案LeetCode--哈希表 以上是我对“哈希表”问题的回答,都被leetcode的判断所接受。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode 1 -200题所有源码 有问题私聊我
leetcode1-240题中文题解,md格式,java版本 有题目有题解有代码 需要使用markdown打开
leetcode26 algo 算法与数据结构,练习代码 语言:java 8 开发工具:vscode,安装插件Java Extension Pack vscode有智能提示,可调试,有重构支持,满足代码练习要求,相比IDEA更轻量级,普通笔记本即可流畅运行。 ...
本书包含了 LeetCode Online Judge所有题目的答案,所有代码经过精心编写,编码规范良好,适合读者反复揣摩,模仿,甚至在纸上默写
leetcode 答案Leetcode---算法 我对 Leetcode 算法问题的回答