Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord

such that:

Example: input="hit",output="cog"
wordList = ["hot","dot","dog","lot","log","cog", "hip"]
Output: 5
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

This is classic BFS(bread first search) problem. Imagine building a tree with root node hit and then it's child nodes being other words created by replacing only one character from the parent node. In this case child nodes of hit will be "hot", "hip".

Continue finding child node for "hit", "hip".

   
        "hit"
        /   \
      "hot" "hip"
      /   \     
   "dot" "lot"
    /      /
 "dog"   "log"
   /       /
 "cog"   "cog"

The solution for the above problem

 public int ladderLength(String beginWord, String endWord, 
    Set<String> wordList) {
    Queue<WordCount> q = new LinkedList();
    WordCount wc = new WordCount(beginWord, 1);
    q.add(wc);
    while (!q.isEmpty()) {
        WordCount w = q.poll();
        if (w.word.equals(endWord))
            return w.count;
        for (int i=0;i< w.word.length(); i++) {
            for(int j=0;j<26;j++) {
                char[] arr = w.word.toCharArray();
                arr[i] =(char) (j+'a');
                String s = new String(arr);
                if (wordList.contains(s)) {
                    wordList.remove(s);
                    q.add(new WordCount(s, w.count + 1));
                }
            }
        }
    }
    return 0;
}


class WordCount {
    public String word;
    public int count;

    public WordCount(String word, int count) {
        this.word = word;
        this.count = count;
    }
}

Recommend Reading

  1. How java manages Memory?
  2. Why is it advised to use hashcode and equals together?
  3. Comparable and Comparator in java
  4. How to create Singleton class in Java?
  5. Difference between equals and ==?
  6. When to use abstract class over interface?
  7. Difference between final, finally and finalize
  8. Why is it recommended to use Immutable objects in Java