LeetCode: Word Ladder

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.

---

We can treat the dictionary as a graph, and those pairs of words that can transform to each other are connected in the graph. The this problem is to find the shortest path from start word to the end word. Since the edge is bidirectional. We can use BFS to find the shortest path. In my solution, a queue is used to help BFS.

C++ Code:

/*
 * func: ladder_length
 * goal: find the shortest length of transformation
 * @param start: start word
 * @param end: end word
 * @param dict: word dictionary
 * return: shortest length
 */
/*
 * Use a queue to do BFS
 * complexity: time O(n), space O(n)
 */
int ladder_length(string start, string end, unordered_set<string> &dict){
    if(dict.size() == 0){
        return 0;
    }
    
    queue<string> word_queue;
    queue<int> distance_queue;
    
    word_queue.emplace(start);
    distance_queue.emplace(1);
    
    while(!word_queue.empty()){
        string curr_word = word_queue.front();
        int curr_dis = distance_queue.front();
        
        word_queue.pop();
        distance_queue.pop();
        
        for(int i=0; i<curr_word.length(); ++i){
            char tmp_c = curr_word[i];
            for(char c = 'a'; c <= 'z'; ++c){
                curr_word[i] = c;
                if(dict.find(curr_word) != dict.end()){
                    word_queue.emplace(curr_word);
                    distance_queue.emplace(curr_dis+1);
                    dict.erase(curr_word);
                }
                if(curr_word == end){
                    return curr_dis + 1;
                }
            }
            curr_word[i] = tmp_c;
        }
    }
    
    return 0;
}

Python Code:

# func: find the shortest length of transformation
# @param start: start word
# @param end: end word
# @param dict: words dict
# @return: shortest length
def ladder_length(start, end, dict):
    word_queue = [start]
    distance_queue = [1]

    while word_queue:
        curr_word = word_queue[0]
        curr_dis = distance_queue[0]

        word_queue.pop(0)
        distance_queue.pop(0)

        for i in xrange(len(curr_word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                transformed_word = curr_word[:i] + c + curr_word[i+1:]
                if transformed_word in dict:
                    word_queue.append(transformed_word)
                    distance_queue.append(curr_dis+1)
                    dict.remove(transformed_word)
                if transformed_word == end:
                    return curr_dis + 1
    return 0