[Leetcode] Word Ladder

Problem

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.

Algorithm

1. 

At first glance, we can build a graph and use BFS to solve this problem. 

• Each node has a label, indicating the word it represents, and a distance to the source (start) word. We can iterate the dict in O(n) time to create O(n) nodes. 
• For each pair of node u and v, if their words only differed by one character, they are connected, i.e. there is an edge between them. Building the edges takes O(n^2) time. 

Then, we start from the source node, doing BFS until found the destination node. The BFS takes O(n) time. So, the total algorithm takes O(n^2) time, limited by the graph construction. 

Why not DFS ? Since DFS may search very deep in the wrong direction, while the shortest distance to in another direction and 1 step away from the source word. 

2. 

Normally, the dictionary has very large size. Therefore, the construction of graph is very time consuming. 

Observation 1: Each letter of an English words only has 26 choices,

Observation 2: Assume the length of the source word is K, there are 26*k transformations of a word. For n words in the dict, there are O(26 * k * n) transformations. 

Since the average length of English words is constant, there are only O(n) transformations for all words in the given dict. 

Build a hash map <key, value> = <word, distance>

Start from source word, 

Put <source, 0> to hash map. 

Put the source word to curLevel of BFS

while(current level is not empty && not found destination word){

         word = curLevel.remove()

         For each t = transformation of word
                 If t is destination
                    return word.distance + 1 

                 if(t is not visited)

                      put(t, word.distance + 1)            

}

Code