126. 单词接龙 II
按字典
wordList
完成从单词beginWord
到单词endWord
转化,一个表示此过程的 转换序列 是形式上像beginWord -> s1 -> s2 -> ... -> sk
这样的单词序列,并满足:
- 每对相邻的单词之间仅有单个字母不同。
- 转换过程中的每个单词
si
(1 <= i <= k
)必须是字典wordList
中的单词。注意,beginWord
不必是字典wordList
中的单词。sk == endWord
给你两个单词
beginWord
和endWord
,以及一个字典wordList
。请你找出并返回所有从beginWord
到endWord
的 最短转换序列 ,如果不存在这样的转换序列,返回一个空列表。每个序列都应该以单词列表[beginWord, s1, s2, ..., sk]
的形式返回。
示例 1:
输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 输出:[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]] 解释:存在 2 种最短的转换序列: "hit" -> "hot" -> "dot" -> "dog" -> "cog" "hit" -> "hot" -> "lot" -> "log" -> "cog"示例 2:
输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] 输出:[] 解释:endWord "cog" 不在字典 wordList 中,所以不存在符合要求的转换序列。
提示:
1 <= beginWord.length <= 5
endWord.length == beginWord.length
1 <= wordList.length <= 500
wordList[i].length == beginWord.length
beginWord
、endWord
和wordList[i]
由小写英文字母组成beginWord != endWord
wordList
中的所有单词 互不相同来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/word-ladder-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
失败,反复调BFS,DFS,还是不通过超时
此题卡的很严,疯狂TLE,没有优化是过不了的,看过题解理解后自己改成了自己容易理解的方式
1. 特判,终点不在列表返回
2. 反图,方便倒着找回起点;如果是正图,可能存在死路,造成额外耗时,反图也是一种剪枝方式
3. 检查是否存在 a->b 的通路,如果 b 点是首次访问,还需要搜索 b 为终点的反图,否则需要看是否步数相同,如果步数相同,也可作为到达此点的方案之一
4. 如果这一层结束后,已经到达终点,无需继续找,后续步数会增加,不会是最佳答案,直接结束
5. 可能找不到可行路径,返回空
6. 可找到的就反向找,通过双端队列插入头部,获得正向解(或者你直接用正常列表反过来也行)
- public class Solution {
- List<List<String>> ans = new ArrayList<>();
- public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
- Set<String> nodes = new HashSet<>(wordList);
- //终点不在wordList返回空
- if(!nodes.contains(endWord)) return ans;
- Map<String,Set<String>> reGraph = new HashMap<>();//反图
- Set<String> orgin = new HashSet<>(wordList);
- Queue<String> queue = new LinkedList<>();
- queue.offer(beginWord);
- //假设长度为 x 已经有可行路径,无需再查长度 x+1 的
- while (!queue.isEmpty() && !reGraph.containsKey(endWord)){
- int size = queue.size();
- //同层节点
- Set<String> line = new HashSet<>();
- //层序找下一个点
- for(int i = 0; i < size; i++){
- String a = queue.poll();
- //原始点列表,找所有下一个可访问点
- for(String b:orgin){
- if(!diffOne(a,b)) continue;
- //如果刚好前面的步数和现在一样(同一层)或者首次访问
- if(line.contains(b) || nodes.contains(b)){
- reGraph.putIfAbsent(b,new HashSet<>());
- reGraph.get(b).add(a);
- line.add(b);
- //首次访问删节点,继续找路
- if(nodes.remove(b)){
- queue.offer(b);
- }
- }
- }
- }
- }
-
- //需判断是否可行路径
- if(!reGraph.isEmpty()){
- Deque<String> deque = new LinkedList<>();
- deque.push(endWord);
- dfs(reGraph,deque,beginWord,endWord);
- }
-
- return ans;
- }
-
- private void dfs(Map<String,Set<String>> graph, Deque<String> deque,String start,String end){
- if(start.equals(end)){
- ans.add(new ArrayList<>(deque));
- return;
- }
-
- for(String pre:graph.get(end)){
- deque.addFirst(pre);
- dfs(graph,deque,start,pre);
- deque.removeFirst();
- }
-
- }
-
- private boolean diffOne(String a, String b){
- int n = a.length();
- int diff = 0;
- for(int i = 0; i < n&&diff<2; i++){
- if(a.charAt(i)!=b.charAt(i)) ++diff;
- }
- return diff == 1;
- }
-
- }