127. Word Ladder Leetcode Java

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

Consider this transformation as a graph, each word is node, and two nodes are connected by an edge if they are transformable. The shortest length from start to end can be found by using Breadth first search. 

I use a queue to implement the BFS, each time when we process a node and visit its neighbors by checking if current node can be transfer to another node in the dictionary. We replace each char in the current node string to any other letters from 'a' to 'z', because the dictionary only contains words. By doing so, we can improve the time complexity,because 26 is a constant. Once we we touch the end word, we can directly output the levels/ lengths.

Time complexity: O(m*n) where m is the dictionary's size and n is the word's length.  

 public int ladderLength(String start, String end, Set<String> dict) {  
     if(start==null||start.length()==0 || start.length()!=end.length()) return 0;  
     LinkedList<String> q=new LinkedList<String>();  
     HashSet<String> used=new HashSet<String>();  
     q.offer(start);  
     used.add(start);  
     int level=1;  
     int curL=0;  
     int lastL=1;  
     while(!q.isEmpty()){  
       String cur=q.poll();  
       lastL--;  
       char[] temp=cur.toCharArray();  
       for(int i=0;i<temp.length;i++){  
         char c=temp[i];  
         for(char j='a';j<='z';j++){  
           temp[i]=j;  
           String replaced=new String(temp);  
           if(replaced.equals(end)) return level+1;  
           if(dict.contains(replaced) && !used.contains(replaced)){  
             q.offer(replaced);  
             used.add(replaced);  
             curL++;  
           }  
         }  
         temp[i]=c;  
       }  
       if(lastL==0){  
         level++;  
         lastL=curL;  
         curL=0;  
       }  
     }  
     return 0;  
   }