Word Ladder II @leetcode

WordLadderII.java

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

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

Still, BFS is the solution to search min/max path. In order to restore the path, we need to keep a parent node list.

Moreover, BFS should stop when current steps > minSteps. Without this, it cannot pass the larget data sets.

 */
 
public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
    if (start == null || end == null || start.length() != end.length() || dict == null || dict.size() == 0) 
        return new ArrayList<ArrayList<String>>();
    
    ArrayList<String> queue = new ArrayList<String>();
    HashMap<String, ArrayList<String>> parents = new HashMap<String, ArrayList<String>>();
    HashMap<String, Integer> distance = new HashMap<String, Integer>();
    if (dict.contains(start))
        dict.remove(start);
    if (!dict.contains(end))
        dict.add(end);
    queue.offer(start);
    distance.put(start, 1);
    int min = Integer.MAX_VALUE;
    
    for (int i=0; i<queue.length(); i++){
        String u = queue.get(i);
        int steps = distance.get(u);
        if (steps == min)
            break; // why ? since this is BFS. The minimum path will be discovered by within min steps only. 
        char[] chs = u.toCharArray();
        for (int j=0; j<chs.length; j++){
            char oldch = chs[j];
            for (char c = 'a'; c <= 'z'; c++){
                if (c == oldch)
                    continue;
                chs[j] = c;
                String v = new String(chs);
                
                if (dict.contains(v){
                    if (!distance.containsKey(v)){
                        queue.add(v);
                        ArrayList<String> pList = new ArrayList<String>();
                        pList.add(u);
                        parents.put(v, pList);
                        distance.put(v, steps + 1);
                    }else if (distance.get(v) == steps + 1){ // Don't forget this case
                        parents.get(v).add(u);
                    }    
                }
                if (v.equals(end)){
                    min = Math.min(min, steps + 1);
                }
            }// enf of for loop
            chs[j] = oldch;
        }
    }
    return restorePath(end, parents, start);
}

ArrayList<ArrayList<String>> restorePath(String end, ArrayList<String> parents, String start){
    ArrayList<ArrayList<String>> paths = new ArrayList<ArrayList<String>>();
    if (end.equals(start)){
        ArrayList<String> pList = new ArrayList<String>();
        pList.add(start);
        paths.add(pList);
    }else if (parents.containsKey(end)){
        for (String v : parents.get(u)){
            ArrayList<ArrayList<String>> list = restorePath(v, parents, start);
            for (ArrayList<String> p : list){
                p.add(end);
                paths.add(p);
            }
        }
    }
    return paths;
}