126. word Solitaire II BFS

126. The word chain II

Press the dictionary  wordList  Complete from word  beginWord  To words  endWord  conversion , A representation of this process   Conversion sequence   It's formally like  beginWord -> s1 -> s2 -> ... -> sk  This sequence of words , And satisfy ：

• There is only a single letter between each pair of adjacent words .
• Every word in the conversion process  si（1 <= i <= k） It has to be a dictionary  wordList  The words in . Be careful ,beginWord  It doesn't have to be a dictionary  wordList  The words in .
• sk == endWord

Here are two words for you  beginWord  and  endWord , And a dictionary  wordList . Please find out and return all from  beginWord  To  endWord  Of   The shortest transformation sequence  , If there is no such conversion sequence , Return an empty list . Each sequence should be in a list of words  [beginWord, s1, s2, ..., sk]  Form return of .

Example 1：

 Input ：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
 Output ：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
 explain ： There is  2  The shortest transformation sequence ：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

Example 2：

 Input ：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
 Output ：[]
 explain ：endWord "cog"  Not in the dictionary  wordList  in , So there is no conversion sequence that meets the requirements .

Tips ：

• 1 <= beginWord.length <= 5
• endWord.length == beginWord.length
• 1 <= wordList.length <= 500
• wordList[i].length == beginWord.length
• beginWord、endWord  and  wordList[i]  It's made up of lowercase letters
• beginWord != endWord
• wordList  All the words in   Different from each other

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/word-ladder-ii
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The result of doing the question

Failure , Repeatedly adjust BFS,DFS, Or not through timeout

Method ：BFS

This question card is very strict , insane TLE, You can't live without optimization , After reading the solution to the problem, I changed my way to understand it easily

1. Special judgement , If the destination is not in the list, return

2. Reverse image , It is convenient to find the starting point backwards ; If it is a positive graph , There may be a dead end , Cause extra time , Inverse graph is also a way of pruning

3. Check for presence a->b Access to , If b Point is the first visit , You also need to search b Is the inverse graph of the end point , Otherwise, you need to see if the steps are the same , If the number of steps is the same , It can also be used as one of the schemes to reach this point

4. If this floor is over , Has reached the end , No need to keep looking , The number of subsequent steps will increase , Not the best answer , End directly

5. May not find a viable path , Returns an empty

6. If you can find it, look in the opposite direction , Insert the header through the double ended queue , Obtain the positive solution （ Or you can just use the normal list and vice versa ）

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);
           // The end is not wordList Returns an empty 
           if(!nodes.contains(endWord)) return ans;
           Map<String,Set<String>> reGraph = new HashMap<>();// Reverse image 
           Set<String> orgin = new HashSet<>(wordList);
           Queue<String> queue = new LinkedList<>();
           queue.offer(beginWord);
           // Assumed length is  x  There is already a viable path , There is no need to check the length  x+1  Of 
           while (!queue.isEmpty() && !reGraph.containsKey(endWord)){
               int size = queue.size();
               // Same layer node 
               Set<String> line = new HashSet<>();
               // Sequence find the next point 
               for(int i = 0; i < size; i++){
                   String a = queue.poll();
                   // Original point list , Find all the next accessible points 
                   for(String b:orgin){
                       if(!diffOne(a,b)) continue;
                       // If the number of steps just ahead is the same as now （ Same floor ） Or visit for the first time 
                       if(line.contains(b) || nodes.contains(b)){
                           reGraph.putIfAbsent(b,new HashSet<>());
                           reGraph.get(b).add(a);
                           line.add(b);
                           // First visit delete node , Keep looking for the way 
                           if(nodes.remove(b)){
                               queue.offer(b);
                           }
                       }
                   }
               }
           }

           // It is necessary to determine whether a feasible path 
           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;
        }

    }