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; }
相关推荐
javascript js_leetcode题解之127-word-ladder.js
python python_leetcode题解之127_Word_Ladder
1. leetCode-126-Word-LadderII.md:这涉及到第126题,词梯问题,通常是一个字符串转换问题,目标是找到两个单词之间的最短转换序列,每次只改变一个字母。 2. leetcode-224-Basic-Calculator.md:这是第224题,基础...
javascript js_leetcode题解之126-word-ladder-ii.js
python python_leetcode题解之126_Word_Ladder_II
6. Word Ladder 单词梯是一个字符串问题,要求将一个单词转换为另一个单词,并且每次转换只能改变一个字符。可以使用广度优先搜索或深度优先搜索来解决该问题。 7. Median of Two Sorted Arrays in Java 两个排序...
leetcode 多少题带有堆栈和队列的字梯 您将针对 Lewis Carroll ...在本作业中,您将实现一个函数word_ladder来生成这些字梯。 有许多可能的算法来生成字梯,但一个简单的算法使用堆栈和队列的组合,如
leetcode 316 LeetCode Summary Exclusive Time of Functions: 栈 Friend Circles:DFS Print Binary Tree:二叉树 Maximal Square:DP Maximal Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:...
126.Word_Ladder_II_词语阶梯二【LeetCode单题讲解系列】
经典字梯游戏c++代码,经测试通过的哦,leetcode上面的题目
例如,`WordLadder.java`可能涉及到词链问题,需要理解图的邻接矩阵或邻接表表示。 6. **字符串处理**:如模式匹配、字符串反转、最长公共前缀等。`ValidPalindrome.java`可能涉及字符串的比较和操作。 7. **位...
力扣 Python 解决方案Leetcode 是准备技术编码面试的...特别案例: Word Ladder II,我的 AC 代码比这个 repo 中的代码慢得多。 但是这个 repo 中的一个得到了 TLE,不知道为什么。 任何想法都将受到高度赞赏。 谢谢!
* Word Ladder:该题目要求将一个单词转换成另一个单词,实现方法使用了广度优先搜索算法。 二、树和图 * Median of Two Sorted Arrays Java:该题目要求找到两个排序数组的中位数,实现方法使用了二分查找算法。 ...
在LeetCode上,单词接龙类问题可能表现为“Anagrams”(同字母异序词)或者“Word Ladder”(单词阶梯),这些题目要求高效地搜索满足条件的单词序列。 【压缩包子文件的文件名称列表】"LeetCode-main"可能包含了一...
5. **搜索和回溯**:对于“NumberofIslands”、“WordLadder”等题目,应聘者必须运用搜索算法,如广度优先搜索(BFS)、深度优先搜索(DFS)以及回溯算法来寻找解决方案。 6. **动态规划和贪心算法**:...
Word Ladder **知识点:** - **问题描述:** - 找到由开始到结尾的字符串的转换字符串集合,中间的转换字符串都要在给定的列表中,并且每一步只能改变一个字符。 - **解决方案分析:** - **原始方法:** - ...
8. **Word Ladder II**:这是一个词链问题,涉及到广度优先搜索和回溯法,寻找从一个单词转换到另一个单词的最短路径。 9. **Regular Expression Matching**:这个涉及到字符串匹配和动态规划。实现一个函数来判断...
9.1 单词变换路径(Word Ladder) 9.1.1 是否存在变换路径 9.1.2 所有最短变换路径9.2 包围区域 10. 深度优先搜索 10.1 N皇后问题 10.2 恢复IP地址 10.3 集合元素之和 10.3.1 元素可以重复 10.3.2 元素不可重复 ...
leetcode Java 246 題目及解答 (英文) Contents 1 Rotate Array in Java 15 2 Reverse Words in a String II 19 3 Evaluate Reverse Polish Notation 21 4 Isomorphic Strings 25 5 Word Ladder 27 6 Word Ladder ...
java lru leetcode ...Ladder Add Two Numbers Matrix Spiral Matrix Mergesort [Algorithm Swap](Mergesort/Algorithm swap.md) Numbers Queue Stack Toposort Trie Tree Two Pointers Union Find