Word Ladder - Length of Shortest Transformation to Reach a Target Word

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> $s_1$ -> $s_2$ -> … -> $s_k$ such that:

Every adjacent pair of words differs by a single letter.
Every $s_i$ for $1 <= i <= k$ is in wordList. Note that beginWord does not need to be in wordList.
$s_k$ == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or $0$ if no such sequence exists.

Example 1

Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
Output: 5
Explanation: One shortest transformation sequence is “hit” -> “hot” -> “dot” -> “dog” -> cog”, which is 5 words long.

Example 2

Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
Output: 0
Explanation: The endWord “cog” is not in wordList, therefore there is no valid transformation sequence.

Approach 1: Breadth First Search

Idea

The solution to this problem is similar to this one: Open the Lock.

Since only one character can be changed a time, we can change the characters one at a time and check if it exists in the wordList. Then, we can assume the word as a neighbor to the previous word.

For the first example - [“hot”,“dot”,“dog”,“lot”,“log”,“cog”], neighbors of “hot” is ”dot” and ”lot”.

Now, we can run a BFS starting from the beginWord and the level where endWord exists, is the length of the shortest transformation sequence.

Implementation

In C++:

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> words (wordList.begin(), wordList.end());
    // if `endWord` doesn't exist, return 0
    if (!words.count(endWord)) return 0;
    unordered_set<string> visited;
    queue<string> q;
    q.push(beginWord);
    visited.insert(beginWord);
    int level = 1;
    while(!q.empty()) {
        int size = q.size();
        while(size--) {
            string s = q.front();
            q.pop();
            // iterate over all the characters of `s`
            for (int i = 0; i < (int)s.length(); ++i) {
                string changed = s;
                // change the characters from 'a' to 'z'
                for (char c = 'a'; c <= 'z'; ++c) {
                    if (c == s[i]) continue;
                    changed[i] = c;
                    // pre-emptively check
                    if (changed == endWord) {
                        return 1 + level;
                    }
                    if (!visited.count(changed) and words.count(changed)) {
                        q.push(changed);
                        visited.insert(changed);
                    }

                }
            } 
        }
        ++level;
    }
    return 0;
}

Complexity Analysis

Time Complexity: $O(N * M * M * 26) = O(NM^2)$ where $N =$ length of wordList and $M =$ average length of the strings. Look-up time for wordList hashset is $O(M)$ .
Space Complexity: $O(N * M)$ .

Approach 2: Bi-directional Breadth First Search

Idea

Since the start node and the target node are fixed, we can run bidirectional BFS (from both start and end) to improve the time complexity from $O(b^d)$ to $O(b^{d/2})$ (where $b =$ branching factor of the tree and $d =$ distance of target from source).

Implementation

In C++:

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> begin({beginWord}),
                          end({endWord}),
                          words(wordList.begin(), wordList.end());
    // if endWord doesn't exist, thus return 0
    if(!words.count(endWord)) return 0;
    int level = 1;
    unordered_set<string> visited;
    while(begin.size() and end.size()) {
        unordered_set<string> next;
        // always consider the smaller set first
        if (begin.size() > end.size()) {
            swap(begin, end);
        }
        for (string s: begin) {
            for (int i = 0; i < (int)s.length(); ++i) {
                string changed = s;
                for (char c = 'a'; c <= 'z'; ++c) {
                    if (c == s[i]) continue;
                    changed[i] = c;
                    // pre-emptively check
                    if (end.count(changed)) {
                        return 1 + level;
                    }
                    if (!visited.count(changed) and words.count(changed)) {
                        next.insert(changed);
                        visited.insert(changed);
                    }

                }
            }
        }
        ++level;
        // we have moved to the next level
        begin = next;
    }
    return 0;
}

Complexity Analysis

Time Complexity: $O(b^{d/2} + b^{d/2}) = O(b^{d/2})$ , where $b =$ branching factor of the tree and $d =$ distance of target from source.
Space Complexity: $O((N + N) * M) = O(N * M)$ (where $N =$ size of wordList), required for begin, end, and visited hashsets.

Published 5 Jun 2021

CS Posts on Twitter