Word Ladder

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

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5
Explanation: As one shortest transformation is "hit"-> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

We are given a beginWord and an endWord. Let these two represent start node and end node of a graph. We have to reach from the start node to the end node using some intermediate nodes/words. The intermediate nodes are determined by the given wordList to us. The only condition for every step we take on this ladder of words is the current word should change by just one letter. We will essentially be working with an undirected and unweighted graph with words as nodes and edges between words which differ by just one letter. The problem boils down to finding the shortest path from a start node to a destination node if there exists one. Hence it can be solved using Breadth First Search approach.

Word Ladder

Intuition

Start from beginWord and search the endWord using BFS.

Algorithm

  1. Do the pre-processing on the given wordList and create a lookup friendly dictionary from it. An obvious choice is a HashSet
  2. Push the beginWord in the queue and initialize len by 1.
  3. While the queue has elements, get the front element of the queue. Let’s call this word as curWord.
  4. Find all the generic transformations of the curWord and find out if any of these transformations is also a transformation of other words in the word list. This is achieved by checking if the transformed word is present in the HashSet.
  5. If a transformed word is found in the dictionary(HashSet), then create a new word from it add the same to Queue
  6. After we finishes the lookup for all the words in current level increment the counter len by 1.
  7. Eventually, if you reach the desired word, the current len is the shortest transformation sequence length.
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
        Set<String> dict = new HashSet<>(wordList);
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int len = 1;
        
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int k = 0 ; k < size ; k++){
                String curWord = queue.poll();
                if(endWord.equals(curWord)){
                    return len;
                }
                char[] arr = curWord.toCharArray();
                for(int i = 0 ; i < arr.length ; i++){
                    char temp = arr[i];
                    for(char a = 'a' ; a <= 'z' ; a++){
                        arr[i] = a;
                        String newWord = String.valueOf(arr);
                        if(dict.contains(newWord)){
                            queue.add(newWord);
                            dict.remove(newWord);
                        }
                    }
                    arr[i] = temp;
                }
            }
            len++;
        }
        return 0;
    }
}

The time complexity is O(N*M), where N is the size of the dictionary and M is the length of the word.

Details:

  • To generate all neighbors – O(26 * M).
  • To check if the word exists in the dictionary – O(1). This is a reason why it is better to put all words to the HashSet.
  • To generate a Queue and traverse the Queue via BFSO(N)

Categories: BFS

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s