126. 单词接龙 II BFS

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，还是不通过超时

方法：BFS

此题卡的很严，疯狂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;
        }

    }