word ladder 2

word_ladder_2.java

public class Solution {
    String from;
    String to;
    Set<String> dict;

    Map<String,Choice> nextLevel;
    Map<String,Choice> curLevel;


    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        this.from = start;
        this.to = end;
        this.dict = dict;
        this.nextLevel = new HashMap<String,Choice>();
        this.curLevel = new HashMap<String,Choice>();

        curLevel.put(start,new Choice(start));

        Choice last = f();
        return getPath(last);
    }

    private LinkedList<List<String>> getPath(Choice c) {
		LinkedList<List<String>> path = new LinkedList<List<String>>();
		
		if (c == null)
			return path;

		if(c.prev.isEmpty()){
			List<String> p = new LinkedList<String>();
			p.add(c.s);
			path.add(p);
			return path;
		}
		
		for (Choice p : c.prev) {
			LinkedList<List<String>> prevPaths = getPath(p);
			for (List<String> prevPath : prevPaths) {
				prevPath.add(c.s);
			}
			path.addAll(prevPaths);
		}

		return path;
	}

    private Choice f() {
        while(!curLevel.isEmpty()){
        	for(String word: curLevel.keySet()){
        		dict.remove(word);
        	}
        	
            for(Choice next: curLevel.values()){
                if(next.s.equals(to)){
                    return next;
                }

                for(int i=0;i<next.s.length();i++){
                    for(char j='a';j<='z';j++){
                        if(j == next.s.charAt(i)) continue;
                        String neww = next.s.substring(0,i) + j + next.s.substring(i+1);
                        if(dict.contains(neww)){
                        	if(nextLevel.containsKey(neww)){
                        		nextLevel.get(neww).prev.add(next);
                        	}else{
                        		Choice c = new Choice(neww);
                        		c.prev.add(next);
                        		nextLevel.put(neww,c);
                        	}
                        }
                    }
                }
            }

            curLevel = nextLevel;
            nextLevel = new HashMap<String,Choice>();
        }

        return null;
    }

    private static class Choice {
        String s;
        List<Choice> prev = new LinkedList<Choice>();
        Choice(String s){this.s = s;}
        
        public String toString(){return s;}
    }
}