Word Ladder (LeetCode String)

Question: 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.

Idea: Breadth-first search. Initial the queue with the input start, then do level by level search until reaching the target or can not go further. To enqueue the next level, we need to use a trick to reduce the time for exhaustivity.

Time: O(nw^26) Space: O(n) (where n is the size of the dict, w is the width of each word in the dict).

Code:

 public class Solution {  
   public int ladderLength(String start, String end, Set<String> dict) {  
     Queue<String> queue=new LinkedList<String>();  
     queue.offer(start);  
     dict.remove(start);  
     int numRuns=1;  
     boolean found=false;  
     while(queue.isEmpty()==false)  
     {  
       int queueLength=queue.size();  
       for(int i=0;i<queueLength;i++)  
       {  
         String cur=queue.poll();  
         if(cur.equals(end))  
           return numRuns;  
         for(int j=0;j<cur.length();j++)  
         {  
           for(char c='a';c<='z';c++)  
           {  
             if(c!=cur.charAt(j))  
             {  
               String tmp=replaceAt(cur,j,c);  
               if(dict.contains(tmp))  
               {  
                 queue.offer(tmp);  
                 dict.remove(tmp);  
               }  
             }  
           }  
         }  
       }  
       numRuns++;  
     }  
     return 0;  
   }  
   public String replaceAt(String s,int index, char c)  
   {  
     char[] chars=s.toCharArray();  
     chars[index]=c;  
     return new String(chars);  
   }  
 }