Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

// bfs(queue) + dfs(HashMap> prevMap), 
 ///////////////////////////////////////////////////////////// 
///////// backtrack the paths is tricky /////////// 
//////////////////////////////////////////////////////////////

public class Solution {
    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
        ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();

        // build up a tree from breath first search.
        HashMap<String, Integer> level = new HashMap<String, Integer>();
        Queue<String> queue = new LinkedList<String>();

        // a word and all its parent nodes in the bfs tree.
        HashMap<String, HashSet<String>> prevMap = new HashMap<String, HashSet<String>>();
        
        if(start == null || end == null || start.length() != end.length()) return ret;
        
        queue.add(start);
        level.put(start,1);
        prevMap.put(start, new HashSet<String>());
        
        int minLen = Integer.MAX_VALUE;
        while(!queue.isEmpty()){
            String curStr = queue.poll();
            int curLevel = level.get(curStr);
            for(int i = 0; i < curStr.length(); i++){
                char[] c = curStr.toCharArray();
                for(char j = 'a'; j <= 'z'; j++){

                    // change one letter, and check if it is in the dict
                    c[i] = j;
                    String tmp = String.valueOf(c);
                    if(tmp.equals(curStr)) continue;
                    if(dict.contains(tmp) && (!level.containsKey(tmp) 
                                           || (level.containsKey(tmp) && level.get(tmp) > curLevel))){
                        
                        if(prevMap.containsKey(tmp)){
                            prevMap.get(tmp).add(curStr);
                        }
                        else{
                            prevMap.put(tmp, new HashSet<String>());
                            prevMap.get(tmp).add(curStr);
                            queue.add(tmp);
                            level.put(tmp, curLevel+1);
                        }        
                    }
                    
                    if(tmp.equals(end)){
                        // the first reaches here would have the shortest path length.
                        if(level.get(curStr) < minLen){
                            ArrayList<String> path = new ArrayList<String>();
                            path.add(end);   // start from the second last level!!! otherwise, we will get duplicates.
                            ret.addAll(traceback(curStr, prevMap, path));    // e.g. [hot,hog,dog],[hot,dot,dog]
                            minLen = curLevel+1;                             // if we start from dog, the result will be:
                        }                                                    //[hot,hog,dog], [hot,hog,dog],[hot,dot,dog]
                        else break;
                    }
                    
                }
            }
        }
        return ret;
    }
    // different from permutation
    public ArrayList<ArrayList<String>> traceback(String end, HashMap<String, HashSet<String>> prevMap, ArrayList<String> path){
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>(); 
        ArrayList<String> newPath = new ArrayList<String>(path);
        newPath.add(0, end);
        if(prevMap.get(end).size() == 0){
            result.add(newPath);
            return result;
        }
        for(String tmp : prevMap.get(end)){
            result.addAll(traceback(tmp, prevMap, newPath)); 
        }
        return result;
    }
    
}