[leetcode] word ladder

Q:  Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

    Return 0 if there is no such transformation sequence.
    All words have the same length.
    All words contain only lowercase alphabetic characters.



http://leetcode.com/onlinejudge#question_127


Solution:

Much more easier than word ladder 2. BFS search.

public class Solution {
    public int ladderLength(String start, String end, HashSet<String> dict) {
        // Start typing your Java solution below
        // DO NOT write main() function
        
        dict.add(start);
        dict.add(end);        
        
        // calcualte ajacent matrix
        HashMap<String, ArrayList<String>> adj = new HashMap<String, ArrayList<String>>();
        for(String str : dict){
            char [] chars = str.toCharArray();            
            for(int i=0;i<start.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)){                        
                        ArrayList<String> neighbours = adj.get(str);
                        if(neighbours == null){
                            neighbours = new ArrayList<String>();
                            neighbours.add(newstr);
                            adj.put(str, neighbours);
                        }else {
                            neighbours.add(newstr);
                        }
                    }                    
                }
                chars[i] = old;                 
            }
        }
        
        HashSet<String> visited = new HashSet<String>();
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(new Node(1, start));
        visited.add(start);
        int pathLen = 0;
        
        while(!queue.isEmpty()){
            Node n = queue.pollFirst();
            if(n.str.equals(end)){
                pathLen = n.level;
                break;
            }else {
                ArrayList<String> neighbours = adj.get(n.str);
                if(neighbours == null || neighbours.isEmpty()) continue;
                for(String s : neighbours){
                    if(! visited.contains(s)){
                        Node p = new Node(n.level+1, s);
                        queue.add(p);
                        visited.add(s);
                    }                  
                }                
            }
        }
        
        return pathLen;        
    }
    
    
    
    public class Node {
        public int level;
        public String str;
        Node(int l, String s){
            str = s;
            level = l;
        }
    }
}