Word Chain

Problem Statement:
               Count the number of minimum jumps required  from the starting word to ending word by changing only one character at each jump.

Start word:  cat    
End word: bay
Dictionary: rat , mat , ray , may , bal , ram , lay

Transition: cat - > mat - > may - > bay
Therefore hops = 3

Solution:

For the given problem we need to find the minimum hops required to reach the end word, the problem is very similar to searching for a node in a tree from the root , and at each level words differ from previous level by 1 character. For such problem we would require BFS (Breadth First Search) .

We start with the root and search for the next word by changing one character and which is also available in the dictionary. This process is repeated until end word is found and hop count is returned, if the word is not reachable by 1 character change then -1 is returned.

Below is the dictionary initialization.

private static Set dict = new HashSet();

 private static void init() 
 {
  dict.add("rat");
  dict.add("mat");
  dict.add("ray");
  dict.add("may");
  dict.add("bal");
  dict.add("ram");
  dict.add("lay");
 }

Now the sub-routine to calculate to the hop count.

/**
  * Word Chain Sub-routine, using BFS
  * @param src: start word
  * @param dst: end word
  * @return : number of hops
  */
 public static int wordChain(String src, String dst)
 {
  int level = 0;

  Queue queue = new LinkedList();
  queue.add(src);
  //used as level separator
  queue.add(null);

  while (!queue.isEmpty()) 
  {
   String popedItem = queue.poll();

   //if null found , then all elements at current level are processed
   if (popedItem == null) 
   {
    queue.offer(null);
    level++;
    continue;
   }

   //Destination word found
   if (popedItem.equalsIgnoreCase(dst))
    return level;

   //Change each character of word from 'a' to 'z', if found in dictionary add to queue, 
   // and remove from dictionary
   int i = 0;
   while (i < popedItem.length()) 
   {
    StringBuilder temp = new StringBuilder(popedItem);
    for (char j = 'a'; j <= 'z'; j++) 
    {
     temp.setCharAt(i, j);

     if (temp.toString().equalsIgnoreCase(dst))
      return level;

     if (dict.contains(temp.toString())) 
     {
      queue.add(temp.toString());
      dict.remove(temp.toString());
     }

    }
    i++;
   }
  }
  return -1;
 }

Please comment and suggestions.
Happy Coding !! :)