Word Ladder II LeetCode

Word Ladder太简单了，这个题的难点是如何在规定时间过LC的test case. 写了一下午，无数次超时。快死了，看了下答案，发现我超时主要是trace back的时候出的问题。按照大牛的方法改了一下，过了。
思路：visited 是用hashmap来存储经过的路径path，注意这里path是hashset，所以顺序还是需要稍后的traceback 方法来找到。
            level是用hashmap存储到start的距离，跟Word ladder里的ladderMap是一样的。
           queue是实现BST

唯一不同的是visited里面存了整个路径出现的string。

看下代码吧，我要是面试面到这个题，我就认了。

注意：1. 其中有两个情况是要把string加入hashset的，第一种情况是string在dict里面，但是不在level里面，第二种情况是string在dict里面，也在level里面，但是到start的距离更小。
2. 在traceback过程中不要怕占用空间，敞开用。不然java不容易过。

public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
        HashMap<String, HashSet<String>> visited = new HashMap<String, HashSet<String>>();
HashMap<String, Integer> level = new HashMap<String, Integer>();
LinkedList<String> queue = new LinkedList<String>();
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();

if(start == null || end == null || start.length()!=end.length()) return result;

HashSet<String> path = new HashSet<String>();
int minLen = Integer.MAX_VALUE;
visited.put(start, path);//only difference from word ladder I
level.put(start, 1);
queue.add(start);

while(!queue.isEmpty()){
String head = queue.remove();
char[] chars = head.toCharArray();
for(int i = 0; i < head.length(); i++){
char old = chars[i];
for(char letter = 'a'; letter <= 'z'; letter++){
chars[i] = letter;
String nextWord = new String(chars);
//two possible situations
//level does not contain nextWord
//level contains nextWord and near the start
if(dict.contains(nextWord) && (!level.containsKey(nextWord)
|| (level.containsKey(nextWord) && level.get(nextWord) > level.get(head)))){
//we update the path, visited, level
if(visited.containsKey(nextWord)){
visited.get(nextWord).add(head);
}else{
path = new HashSet<String>();
path.add(head);
visited.put(nextWord, path);
level.put(nextWord, level.get(head) + 1);
queue.add(nextWord);
}
}

if(nextWord.equals(end)){
if(level.get(head) < minLen){
ArrayList<String> entry = new ArrayList<String>();
entry.add(end);
result.addAll(backtrace(head,visited,entry));
minLen = level.get(head)+1;
}else{
break;
}
}
chars[i] = old;

}
}
}
return result;
}

private ArrayList<ArrayList<String>> backtrace(String end,
HashMap<String, HashSet<String>> visited, ArrayList<String> path) {
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
ArrayList<String> entry = new ArrayList<String>(path);
entry.add(0,end);
if(visited.get(end).size()<1){
result.add(entry);
return result;
}

for(String str : visited.get(end)){
result.addAll(backtrace(str,visited,entry));
}
return result;
}