Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. 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.

Solution:
BFS.

public class Solution {
    public int ladderLength(String start, String end, HashSet dict) {
        if(dict.size() == 0) return 0;
        return bfs(start, end, dict);
    }
    public int bfs(String start, String end, HashSet dict){
           Queue queue = new LinkedList();
           Queue len = new LinkedList();
           queue.add(start);
           len.add(1);
           while(!queue.isEmpty()){
               String word = queue.poll();
               int length = len.poll();
               if(word.equals(end)) return length;
               for(int i = 0; i < word.length(); i++){ // for each word, check each letter at each position
                   char[] c = word.toCharArray();
                   for(int j = 'a'; j <= 'z'; j++){
                       if(j == c[i]) continue;
                       c[i] = (char)(j);
                       String str = String.valueOf(c);
                       if(dict.contains(str)){
                           queue.add(str);
                           len.add(length+1);
                           dict.remove(str);
                       }
                   }
               }
           }
           return 0;
    }
}