126. Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Return
  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:
Return an empty list if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Solution：BFS + Dijkstra dist纪录思想 + DFS

思路：
BFS像Word Ladder I 一样去找到end_word，在bfs过程中建立start_word到每个node_word的最小距离记录：ladder (可以用来check是否为ladder word 以及 是否node_word是最短的(最先碰到的)，如果是的话，建立反向graph，以便最后dfs回来找路径。

Screen Shot 2017-11-19 at 19.11.06.png

Time Complexity: O(E+V) Space Complexity: O(E+V)

Solution Code：

public class Solution {
    
    public List<List<String>> findLadders(String start, String end, List<String> wordList) {    

        List<List<String>> result = new ArrayList<List<String>>();
        if(wordList.size() == 0) return result;
        

        Map<String,List<String>> graph = new HashMap<>();
        Map<String,Integer> ladder = new HashMap<String,Integer>(); //作为min距离，也可以作为wordSet有效的check, 也可以作为避免回访的set
        Queue<String> queue = new LinkedList<>();

        int min = Integer.MAX_VALUE;

        // ladder distance init
        for (String str: wordList)
            ladder.put(str, Integer.MAX_VALUE);
        
        queue.add(start);
        ladder.put(start, 0);
                
        //BFS: Dijisktra search
        while(!queue.isEmpty()) {
            String word = queue.poll();
            
            int step = ladder.get(word) + 1;//'step' indicates how many steps are needed to travel to one word. 
            
            if(step > min) break;
            
            for(int i = 0; i < word.length(); i++){
               StringBuilder builder = new StringBuilder(word); 
                for(char ch = 'a';  ch <= 'z'; ch++){
                    builder.setCharAt(i, ch);
                    String new_word = builder.toString();             
                    if(ladder.containsKey(new_word)) { 
                    // check 有效ladder
                            
                        if(step > ladder.get(new_word))
                        // Check if it is the shortest path to one word. 同时也不回访
                            continue;

                        if(step < ladder.get(new_word)) {
                            queue.add(new_word);
                            ladder.put(new_word, step);
                        }
                        // step == ladder.get(new_word)
                        // If one word already appeared in one ladder,
                        // Do not insert the same word inside the queue twice. Otherwise it gets TLE.
                        
                        if (!graph.containsKey(new_word)) {
                            graph.put(new_word, new LinkedList<>());
                        }
                        graph.get(new_word).add(word); // just 反向

                        if (new_word.equals(end)) {
                            min = step;
                        }

                    } //End if dict contains new_word
                } //End:Iteration from 'a' to 'z'
            } //End:Iteration from the first to the last
        } //End While

        // BackTracking
        LinkedList<String> cur_res = new LinkedList<>();
        backTrace(graph, end, start, cur_res, result);

        return result;        
    }
    private void backTrace(Map<String, List<String>> graph, String word, String start, List<String> cur_res, List<List<String>> result){
        if (word.equals(start)){
            cur_res.add(0, word);
            result.add(new ArrayList<>(cur_res));
            cur_res.remove(0);
            return;
        }

        cur_res.add(0, word);
        if (graph.get(word) != null) {
            for (String s: graph.get(word)) {
                backTrace(graph, s, start, cur_res, result);
            }
        }
        cur_res.remove(0);
    }
}