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:

1. Only one letter can be changed at a time
2. 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"]
  ]

一刷
题解：我觉得这个问题难在，什么是shorted transform，因为用dfs做，很可能就进入一个永远出不来的状态。
首先用dijkstra构造两个map,
ladder: String->Integer, 存储有从start到该string最短需要几步
map: String -> List<String> (adjacent graph), List<String>中的str修改一个字母可以到String

public class Solution {
    Map<String, List<String>> map;
    List<List<String>> res;
    
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> words) {
        Set<String> dict = new HashSet<String>(words);
        
        
        res = new ArrayList<>();
        if(dict.size() == 0) return res;
        
        int min = Integer.MAX_VALUE;
        Queue<String> queue = new ArrayDeque<String>();
        queue.add(beginWord);
        
        map = new HashMap<>();
        Map<String, Integer> ladder = new HashMap<String, Integer>();
        for(String str : dict){
            ladder.put(str, Integer.MAX_VALUE);
        }
        ladder.put(beginWord, 0);
        dict.add(endWord);
        //BFS: Dijisktra search
        while(!queue.isEmpty()){
            String word = queue.poll();
            int step = ladder.get(word)+1;
            if(step>min) break;
            
            
            for(int i=0; i<word.length(); i++){
                StringBuilder sb = new StringBuilder(word);
                for(char ch = 'a'; ch<='z'; ch++){
                    if(ch == word.charAt(i)) continue;
                    sb.setCharAt(i, ch);
                    String new_word = sb.toString();
                    if(ladder.containsKey(new_word)){
                        if(step>ladder.get(new_word)) continue;//exit shorter path
                        else if(step < ladder.get(new_word)){
                            queue.add(new_word);
                            ladder.put(new_word, step);//update
                        }
                        
                        if(map.containsKey(new_word)){//build adjacent graph
                            map.get(new_word).add(word);
                        }else{
                            List<String> list = new LinkedList<>();
                            list.add(word);
                            map.put(new_word, list);
                        }
                        
                        if(new_word.equals(endWord)) min = step;
                        
                    }//end if dict contains new_Word
                }//end: iteration from 'a' to 'z'
            } //end: iteration from the start index to the end index of the string
        }//end while
        
        
        //backtracking
        LinkedList<String> list = new LinkedList<String>();
        backTrace(endWord, beginWord, list);
        return res;
        
    }
    
    
    private void backTrace(String endWord, String startWord, List<String> list){
        if(endWord.equals(startWord)){
            list.add(0, startWord);
            res.add(new ArrayList<>(list));
            list.remove(0);
            return;
        }
        list.add(0, endWord);
        if(map.get(endWord)!=null){
            for(String s:map.get(endWord))
                backTrace(s, startWord, list);
        }
        list.remove(0);
    }
}