[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超时，提交了十次都木有过，太尼玛丧心病狂了！

careercup上也有这道题，但是只需要找出一条最短路径即可，相对来说简单的多，这道题实在吐槽无力，从网上找到了一个大神写的，相对而言逻辑最清晰的一篇。由于源代码是在论坛回帖中，作者无从考证。大家还是直接看代码吧。

这里有两点可以留意一下：（本解法用的邻接表法）

1. 构建graph的时候的时候用的String，回溯的时候用的node节点

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;
	        }
	    }