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:

Using BFS

public class Solution {
    public int ladderLength(String start, String end, HashSet<String> dict) {
        // Start typing your Java solution below
        // DO NOT write main() function
        LinkedList<String> que = new LinkedList<String>();
        Set<String> used = new HashSet<String>();
       
        int ret = 1;
        que.add(start);
        used.add(start);
       
        int lev1 = 1; int lev2 = 0;
       
        while(!que.isEmpty()){
            String t = que.removeFirst();
            lev1 --;
            // add new values
            for(int i = 0; i < t.length(); i++){
                String f = t.substring(0,i);
                String e = t.substring(i+1);
                for(int c = (int)'a'; c <= (int)'z'; c++){
                    String news = f + (char)c + e;
                    if(!news.equals(t) && dict.contains(news) && !used.contains(news)){
                        if(news.equals( end)) return ret+1;
                        que.add(news);
                        used.add(news);
                        lev2 ++;
                    }
                }
            }
           
            if(lev1 == 0){
                lev1 = lev2;
                lev2 = 0;
                ret ++;
            }
           
        }
        return 0;
       
    }
}