LeetCode: Word Ladder I

LeetCode: Word Ladder I

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. 

My solution:

The idea is to use BFS. First replace each character in a string with all other 25 letters to see if the new string is in the dictionary. If so, add it into the queue. To avoid strings that have been used previously, we use a set *usedWords*;

Another key point is to use two queues, one of which holds all new created strings on the same level, so that we can get a place to increase the level information.

The following code passes all test cases at one time.

public class Solution {
 
  public int ladderLength(String start, String end, HashSet<String> dict) {
        int len =0;
        char originalChar;
        String str;
        int i;
       
    if (start==null||end==null||dict==null||start.length()==0||start.length()!=end.length()){
            return 0;
        }
        //use a set to record all words
        HashSet<String> usedWords = new HashSet<String>();
       
        Queue<String> qToReadFrom = new LinkedList<String>();
   
        qToReadFrom.offer(start);//or q.add()

        while(!qToReadFrom.isEmpty()){
           
            Queue<String> qLevel = new LinkedList<String>();
           
            while(!qToReadFrom.isEmpty()){
               
                str = qToReadFrom.poll();
               
                for(i=0; i<str.length(); i++){
                    originalChar = str.charAt(i);
                    StringBuilder sb = new StringBuilder(str);
                    for(char j='a'; j<='z'; j++){
                        if(j == originalChar) continue;
                        sb.setCharAt(i, j);
                       
                        if(sb.toString().equals(end)){
                           
                            return len +2;
                        }
                       
                      if(!usedWords.contains(sb.toString()) && dict.contains(sb.toString())){                       
                            usedWords.add(sb.toString());
                            qLevel.add(sb.toString());
                        }
                       
                    }
                }
                           
            }
            //Level++
            qToReadFrom = qLevel;      
            len++;
        }  
       
        return 0;
    }
   
}