Leetcode: Word Ladder

Difficulty: Medium

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:

1.    Only one letter can be changed at a time

2.    Each intermediate word must exist in the word list

For example,

Given:

beginWord = "hit"

endWord = "cog"

wordList = ["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.

Runtime Analysis:

First, we need to understand the problem and the approach we should take. Please read the Algorithmic Approach first.

Runtime: O(26n) 
Space: O(n) 

Algorithmic Approach:

This question requires a good understanding of BFS. Given an initial word to start with, we need to transform character by character to reach our final word. However, we cannot transform each character directly from our initial to final state because that particular word may not exist in our dictionary. We might have to transform to intermediary states to in order reach our final string.

See Example:

Dictionary = {"cat", "aat", "aag", "aog", "dog"}
Transformation = ["cat" => "aat" => "aag" => "aog" => "dog"]

Since we do not know which words exist in our dictionary, we would have to go through every alphabetical character (a-z) for every index in our string and check if that is a valid state.

The reason we are using BFS instead of DFS is because we are asked the compute the shortest transformation sequence. Due to this fact, we want to visit the neighbors that are closest distance first. 

We can implement BFS by using a Queue. We push our initial node on first. For each iteration, we pop off all elements in the queue (to process all nodes that are x distance away from our start). For each element, we check if it is equal to our final state, if so, we just return the distance. Otherwise, we push each of the node's neighbors back onto the queue.

In order to prevent cycles in the graph traversal, we remove words that we have already visited from the dictionary.

Java Code: 

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        
        Queue<String> queue = new LinkedList<String>();
        queue.add(beginWord);
        int count = 1;
        
        while(!queue.isEmpty()){
            
            int size = queue.size();
            
            for(int j = 0; j < size; j++){
                String word = queue.remove();
                
                if(word.equals(endWord)){
                    return count;
                }
                
                for(int i = 0; i < word.length(); i++){
                    for(char c = 'a'; c <= 'z'; c++){
                        if(c != word.charAt(i)){
                            char[] s = word.toCharArray();
                            s[i] = c;
                            String trans = new String(s);
                            
                            if(wordList.contains(trans)){
                                queue.add(trans);
                                wordList.remove(trans);
                            }
                        }
                    }
                }
            }
            
            count++;
        }
        
        return 0;
    }
}