[leecode]Word Ladder II

Word Ladder II
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.
이 문제는 leetcode에서 통과율이 가장 낮은 문제입니다.Max Points on a Line는 비교적 늦게 냈기 때문에 어렵지 않습니다. 이 문제, 좋습니다. DFS 시간 초과, BFS 시간 초과, 10번 제출했지만 없었습니다. 테니마는 미친 듯이 날뛰었습니다!
careercup에도 이 문제가 있지만 가장 짧은 경로를 찾아내면 된다. 상대적으로 간단하다. 이 문제는 정말 힘이 없다. 인터넷에서 신이 쓴 상대적으로 논리가 가장 뚜렷한 한 편을 찾았다.원본 코드가 포럼답장에 있기 때문에 작가는 고증할 길이 없다.모두들 코드를 직접 보는 것이 좋겠다.
여기에 두 가지 주의할 점이 있다. (본 해법에 사용된 인접표법)
1. 그래프를 만들 때 쓰는 스트링, 거슬러 올라갈 때 쓰는 노드
2.'아버지 노드'와 형제 간의 인접 관계를 차단하여parent 노드는 하나만
 

	    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
	        
	        // Start typing your Java solution below
	        // DO NOT write main() function              
	        
	        HashMap<String, HashSet<String>> neighbours = new HashMap<String, HashSet<String>>();
	        
	        dict.add(start);
	        dict.add(end);
	        
	        // init adjacent graph        
	        for(String str : dict){
	            calcNeighbours(neighbours, str, dict);
	        }
	        
	        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
	        
	        // BFS search queue
	        LinkedList<Node> queue = new LinkedList<Node>();
	        queue.add(new Node(null, start, 1));
	        
	        // BFS level
	        int previousLevel = 0;
	        
	        // mark which nodes have been visited, to break infinite loop
	        HashMap<String, Integer> visited = new HashMap<String, Integer>(); 
	        while(!queue.isEmpty()){
	            Node n = queue.pollFirst();            
	            if(end.equals(n.str)){ 
	                // fine one path, check its length, if longer than previous path it's valid
	                // otherwise all possible short path have been found, should stop
	                if(previousLevel == 0 || n.level == previousLevel){
	                    previousLevel = n.level;
	                    findPath(n, result);                    
	                }else {
	                    // all path with length *previousLevel* have been found
	                    break;
	                }                
	            }else {
	                HashSet<String> set = neighbours.get(n.str);                 
	                
	                if(set == null || set.isEmpty()) continue;
	                // note: I'm not using simple for(String s: set) here. This is to avoid hashset's
	                // current modification exception.
	                ArrayList<String> toRemove = new ArrayList<String>();
	                for (String s : set) {
	                    
	                    // if s has been visited before at a smaller level, there is already a shorter 
	                    // path from start to s thus we should ignore s so as to break infinite loop; if 
	                    // on the same level, we still need to put it into queue.
	                    if(visited.containsKey(s)){
	                        Integer occurLevel = visited.get(s);
	                        if(n.level+1 > occurLevel){
	                            neighbours.get(s).remove(n.str);
	                            toRemove.add(s);
	                            continue;
	                        }
	                    }
	                    visited.put(s,  n.level+1);
	                    queue.add(new Node(n, s, n.level + 1));
	                    if(neighbours.containsKey(s))
	                        neighbours.get(s).remove(n.str);
	                }
	                for(String s: toRemove){
	                    set.remove(s);
	                }
	            }
	        }

	        return result;
	    }
	    
	    public void findPath(Node n, ArrayList<ArrayList<String>> result){
	        ArrayList<String> path = new ArrayList<String>();
	        Node p = n;
	        while(p != null){
	            path.add(0, p.str);
	            p = p.parent; 
	        }
	        result.add(path);
	    }

	    /*
	     * complexity: O(26*str.length*dict.size)=O(L*N)
	     */
	    void calcNeighbours(HashMap<String, HashSet<String>> neighbours, String str, HashSet<String> dict) {
	        int length = str.length();
	        char [] chars = str.toCharArray();
	        for (int i = 0; i < length; i++) {
	            
	            char old = chars[i]; 
	            for (char c = 'a'; c <= 'z'; c++) {

	                if (c == old)  continue;
	                chars[i] = c;
	                String newstr = new String(chars);                
	                
	                if (dict.contains(newstr)) {
	                    HashSet<String> set = neighbours.get(str);
	                    if (set != null) {
	                        set.add(newstr);
	                    } else {
	                        HashSet<String> newset = new HashSet<String>();
	                        newset.add(newstr);
	                        neighbours.put(str, newset);
	                    }
	                }                
	            }
	            chars[i] = old;
	        }
	    }
	    
	    private class Node {
	        public Node parent;
	        public String str;
	        public int level;
	        public Node(Node p, String s, int l){
	            parent = p;
	            str = s;
	            level = l;
	        }
	    }