- 浏览: 136969 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) 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"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.
[分析] 这是一道呼唤耐心的题目,基本思路和word ladder一致,利用BFS搜索出最短路径,所不同的是这题需要找出所有最短路径,因此在搜索时需要记录搜索路径以便于最后进行回溯。有几个关键的细节需要注意:
1)搜索到一个可供跳转的单词时不能像word ladder题中那样立即删除,需要遍历完当前层后再统一从dict中删除下一层的单词,考虑这种情况:input= {"bet", "hat", ["bet", "bit", "bot", "hit", "hot", "hat"]},遍历第三层hit时,若直接删除hat,则最终output会少一条从hot到hat的路径。遍历每层时使用visited集合记录所有下一层单词,该层遍历结束后从dict中删除该层对应的visited集合。
2)反方向搜索,即从end往start搜,可提高回溯时的效率,因为构造路径时可顺序添加而无需插入在数组头部(会有隐藏的数组移位操作)。
3)为了方便回溯,反向搜索过程中要记录当前元素的前驱(output路径方向看),可使用HashMap,key为当前元素,value是key的前驱列表。正向搜索记录后继也是可行的,但实现起来会麻烦些,因为在遍历过程中找到的后继不一定最终能导向end,在回溯时需要进行额外判断,不然可能会空指针。
4) 忽略if (visited.add(newStr))这个条件直接queue.offer(newStr)会导致超时,因为queue中会加入重复元素
先参照http://blog.csdn.net/linhuanmars/article/details/23071455 稍微修改了如Method1所示,然后再此基础上修改了自己初始的想法得到Method 2实现
[ref]
http://www.cnblogs.com/TenosDoIt/p/3443512.html
http://blog.csdn.net/linhuanmars/article/details/23071455
http://blog.csdn.net/u013325815/article/details/42043051
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"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.
[分析] 这是一道呼唤耐心的题目,基本思路和word ladder一致,利用BFS搜索出最短路径,所不同的是这题需要找出所有最短路径,因此在搜索时需要记录搜索路径以便于最后进行回溯。有几个关键的细节需要注意:
1)搜索到一个可供跳转的单词时不能像word ladder题中那样立即删除,需要遍历完当前层后再统一从dict中删除下一层的单词,考虑这种情况:input= {"bet", "hat", ["bet", "bit", "bot", "hit", "hot", "hat"]},遍历第三层hit时,若直接删除hat,则最终output会少一条从hot到hat的路径。遍历每层时使用visited集合记录所有下一层单词,该层遍历结束后从dict中删除该层对应的visited集合。
2)反方向搜索,即从end往start搜,可提高回溯时的效率,因为构造路径时可顺序添加而无需插入在数组头部(会有隐藏的数组移位操作)。
3)为了方便回溯,反向搜索过程中要记录当前元素的前驱(output路径方向看),可使用HashMap,key为当前元素,value是key的前驱列表。正向搜索记录后继也是可行的,但实现起来会麻烦些,因为在遍历过程中找到的后继不一定最终能导向end,在回溯时需要进行额外判断,不然可能会空指针。
4) 忽略if (visited.add(newStr))这个条件直接queue.offer(newStr)会导致超时,因为queue中会加入重复元素
先参照http://blog.csdn.net/linhuanmars/article/details/23071455 稍微修改了如Method1所示,然后再此基础上修改了自己初始的想法得到Method 2实现
[ref]
http://www.cnblogs.com/TenosDoIt/p/3443512.html
http://blog.csdn.net/linhuanmars/article/details/23071455
http://blog.csdn.net/u013325815/article/details/42043051
// Method 2: 去除Method1 的辅助数据结构 public class Solution1 { public List<List<String>> findLadders(String start, String end, Set<String> dict) { List<List<String>> result = new ArrayList<List<String>>(); LinkedList<String> queue = new LinkedList<String>(); queue.add(end); HashMap<String, ArrayList<String>> nextMap = new HashMap<String, ArrayList<String>>(); HashSet<String> visited = new HashSet<String>(); dict.add(start); dict.remove(end); int currLevel = 1, nextLevel = 0; int L = start.length(); boolean found = false; while (!queue.isEmpty()) { String currStr = queue.poll(); if (currLevel == 0) { if (found) break; currLevel = nextLevel; nextLevel = 0; dict.removeAll(visited); visited.clear(); } char[] currCharArray = currStr.toCharArray(); for (int i = 0; i < L; i++) { char oldChar = currCharArray[i]; boolean foundCurCycle = false; for (char c = 'a'; c <= 'z'; c++) { if (c == oldChar) continue; currCharArray[i] = c; String newStr = new String(currCharArray); if (dict.contains(newStr)) { if (!nextMap.containsKey(newStr)) { nextMap.put(newStr, new ArrayList<String>()); } nextMap.get(newStr).add(currStr); // 务必先更新nextMap再判断搜索是否结束,否则nextMap可能最终为空 if (newStr.equals(start)) { found = true; foundCurCycle = true; break; } if (visited.add(newStr)) { queue.offer(newStr); nextLevel++; } } } currCharArray[i] = oldChar; if (foundCurCycle) break; } currLevel--; } if (found) { List<String> item = new ArrayList<String>(); item.add(start); getPath(start, end, item, nextMap, result); } return result; } public void getPath(String start, String end, List<String> item, HashMap<String, ArrayList<String>> nextMap, List<List<String>> result) { if (start.equals(end)) { result.add(new ArrayList<String>(item)); } else { ArrayList<String> nextList = nextMap.get(start); for (String next : nextList) { item.add(next); getPath(next, end, item, nextMap, result); item.remove(item.size() - 1); } } } }
// Method 1, 参考下面链接修改 // http://blog.csdn.net/linhuanmars/article/details/23071455 public class Solution { class StringWithLevel { String str; int level; public StringWithLevel(String str, int level) { this.str = str; this.level = level; } } public List<List<String>> findLadders(String start, String end, Set<String> dict) { List<List<String>> result = new ArrayList<List<String>>(); LinkedList<StringWithLevel> queue = new LinkedList<StringWithLevel>(); queue.add(new StringWithLevel(end, 0)); HashMap<String, ArrayList<String>> nextMap = new HashMap<String, ArrayList<String>>(); HashSet<String> visited = new HashSet<String>(); dict.add(start); dict.remove(end); int currLevel = 0, preLevel = 0; int L = start.length(); boolean found = false; while (!queue.isEmpty()) { StringWithLevel curr = queue.poll(); String currStr = curr.str; currLevel = curr.level; if (currLevel > preLevel) { if (found) break; preLevel = currLevel; dict.removeAll(visited); visited.clear(); } char[] currCharArray = currStr.toCharArray(); for (int i = 0; i < L; i++) { char oldChar = currCharArray[i]; boolean foundCurCycle = false; for (char c = 'a'; c <= 'z'; c++) { if (c == oldChar) continue; currCharArray[i] = c; String newStr = new String(currCharArray); if (dict.contains(newStr)) { ArrayList<String> nextList = null; if (nextMap.containsKey(newStr)) { nextList = nextMap.get(newStr); } else { nextList = new ArrayList<String>(); } nextList.add(currStr); nextMap.put(newStr, nextList); if (newStr.equals(start)) { found = true; foundCurCycle = true; break; } if (visited.add(newStr)) queue.offer(new StringWithLevel(newStr, currLevel + 1)); // enqueue a new item of next level } } currCharArray[i] = oldChar; if (foundCurCycle) break; // can not use found here, or will miss some paths } } if (found) { List<String> item = new ArrayList<String>(); item.add(start); getPath(start, end, item, nextMap, result); } return result; } public void getPath(String start, String end, List<String> item, HashMap<String, ArrayList<String>> nextMap, List<List<String>> result) { if (start.equals(end)) { result.add(new ArrayList<String>(item)); } else { ArrayList<String> nextList = nextMap.get(start); for (String next : nextList) { item.add(next); getPath(next, end, item, nextMap, result); item.remove(item.size() - 1); } } } }
发表评论
-
Leetcode - Palindrome Permutation II
2015-08-28 21:17 2210Given a string s, return all th ... -
Leetcode - Factor Combination
2015-08-28 09:53 856Numbers can be regarded as prod ... -
Leetcode - Generate Parentheses
2015-08-08 17:01 520[分析] 第一个思路(错误的~):假设递归函数返回 n - ... -
Leetcode - Word Search II
2015-08-03 21:25 970iven a 2D board and a list of w ... -
Leetcode - Word Search
2015-08-03 21:03 513Given a 2D board and a word, fi ... -
Leetcode - Subset
2015-08-02 12:06 949[分析] 三种思路 思路1:每层递归新加一个元素,第一层递归, ... -
Leetcode - Subset II
2015-08-02 12:13 955[分析] 延续Subset三种思路,关键是添加去重处理 思路 ... -
Leetcode - Gray Code
2015-08-01 17:26 577原题链接:https://leetcode.com/probl ... -
Leetcode - Permutation Sequence
2015-08-01 17:19 513原题链接:https://leetcode.com/probl ... -
Leetcode - Permutation II
2015-08-01 10:49 603原题链接:https://leetcode.com/probl ... -
Leetcode - Combination
2015-08-01 08:36 487[分析] 从 n 个数中取 k 个数,第一个数有 n 种取法… ... -
Leetcode - Combination Sum III
2015-07-31 22:04 520[分析] 思路就是枚举k个数所有可能的组合并判断是否符合条件。 ... -
Leetcode - Combination Sum II
2015-07-31 21:06 611[分析] 输入数组中的每个元素至多使用一次,相较于Combin ... -
Leetcode - Combination Sum
2015-07-31 20:21 586Given a set of candidate number ... -
Leetcode - Sudoku Solver
2015-07-31 09:14 462[分析] 做Valid Sudoku时表示3*3区块的下标想得 ... -
Leetcode - N Queues II
2015-07-30 20:52 405[分析] 做完N皇后第一题,这个就so easy~ pu ... -
Leetcode - N-Queens
2015-07-30 20:38 442[分析] N皇后摆放规则:两个皇后不能共存于同一行、同一列以及 ... -
Leetcode - Majority Element II
2015-06-30 22:12 840[分析] Majority Element II这个扩展版可以 ... -
Leetcode - Course Schedule II
2015-06-29 22:03 482There are a total of n courses ... -
Leetcode - Clone Graph
2015-06-29 21:59 501Clone an undirected graph. Each ...
相关推荐
python python_leetcode题解之126_Word_Ladder_II
1. leetCode-126-Word-LadderII.md:这涉及到第126题,词梯问题,通常是一个字符串转换问题,目标是找到两个单词之间的最短转换序列,每次只改变一个字母。 2. leetcode-224-Basic-Calculator.md:这是第224题,基础...
python python_leetcode题解之127_Word_Ladder
126.Word_Ladder_II_词语阶梯二【LeetCode单题讲解系列】
例如,`WordLadder.java`可能涉及到词链问题,需要理解图的邻接矩阵或邻接表表示。 6. **字符串处理**:如模式匹配、字符串反转、最长公共前缀等。`ValidPalindrome.java`可能涉及字符串的比较和操作。 7. **位...
6. Word Ladder 单词梯是一个字符串问题,要求将一个单词转换为另一个单词,并且每次转换只能改变一个字符。可以使用广度优先搜索或深度优先搜索来解决该问题。 7. Median of Two Sorted Arrays in Java 两个排序...
力扣 Python 解决方案Leetcode 是准备技术编码面试的...特别案例: Word Ladder II,我的 AC 代码比这个 repo 中的代码慢得多。 但是这个 repo 中的一个得到了 TLE,不知道为什么。 任何想法都将受到高度赞赏。 谢谢!
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:...
经典字梯游戏c++代码,经测试通过的哦,leetcode上面的题目
在LeetCode上,单词接龙类问题可能表现为“Anagrams”(同字母异序词)或者“Word Ladder”(单词阶梯),这些题目要求高效地搜索满足条件的单词序列。 【压缩包子文件的文件名称列表】"LeetCode-main"可能包含了一...
* Word Break、Word Break II:该题目要求将字符串分割成单词,实现方法使用了动态规划和回溯算法。 * Word Ladder:该题目要求将一个单词转换成另一个单词,实现方法使用了广度优先搜索算法。 二、树和图 * ...
6 Word Ladder II 29 7 Median of Two Sorted Arrays 33 8 Kth Largest Element in an Array 35 9 Wildcard Matching 37 10 Regular Expression Matching in Java 39 11 Merge Intervals 43 12 Insert Interval 45 ...
8. **Word Ladder II**:这是一个词链问题,涉及到广度优先搜索和回溯法,寻找从一个单词转换到另一个单词的最短路径。 9. **Regular Expression Matching**:这个涉及到字符串匹配和动态规划。实现一个函数来判断...
5. **搜索和回溯**:对于“NumberofIslands”、“WordLadder”等题目,应聘者必须运用搜索算法,如广度优先搜索(BFS)、深度优先搜索(DFS)以及回溯算法来寻找解决方案。 6. **动态规划和贪心算法**:...
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 元素不可重复 ...
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
6. **图论**:深度优先搜索(DFS)和广度优先搜索(BFS)在解决图问题如"Word Ladder"时必不可少。 7. **位运算**:在某些问题中,如"Number of 1 Bits",位运算可以提供高效的解决方案。 8. **设计模式**:工厂...