127. Word Ladder • Algorithm Solutions

1. Description

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.

2. Example

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.

3. Constraints

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord, endWord, and wordList[i] consist of lowercase English letters.
beginWord != endWord
All the words in wordList are unique.

4. Solutions

Hash Table && Unidirectional Breadth-First Search

m = begin_word.size(), n = words_list.size()
Time complexity: O($m^2n$)
Space complexity: O($m^2n$)

class Solution {
public:
    int ladderLength(
        const string &begin_word,
        const string &end_word,
        const vector<string> &words_list) {
        const int m = begin_word.size(), n = words_list.size();

        unordered_map<string, vector<string>> valid_words_list;
        valid_words_list.reserve(m * n);

        for (const auto &word : words_list) {
            string word_template = word;
            for (int i = 0; i < m; ++i) {
                char letter = word_template[i];
                word_template[i] = '*';
                valid_words_list[word_template].push_back(word);
                word_template[i] = letter;
            }
        }

        queue<string> words{{begin_word}};
        unordered_set<string> visited{{begin_word}};
        visited.reserve(n + 1);
        int step = 1;
        while (!words.empty()) {
            int word_count = words.size();
            for (int i = 0; i < word_count; ++i) {
                string word = words.front();
                words.pop();

                if (word == end_word) {
                    return step;
                }

                for (int j = 0; j < m; ++j) {
                    char letter = word[j];
                    word[j] = '*';

                    auto it = valid_words_list.find(word);
                    if (it != valid_words_list.end()) {
                        for (const auto &w : it->second) {
                            if (visited.find(w) == visited.end()) {
                                visited.insert(w);
                                words.push(w);
                            }
                        }
                        valid_words_list.erase(it);
                    }

                    word[j] = letter;
                }
            }
            ++step;
        }

        return 0;
    }
};

Hash Table && Bidirectional Breadth-First Search

m = begin_word.size(), n = words_list.size()
Time complexity: O($m^2n$)
Space complexity: O(mn)

class Solution {
public:
    int ladderLength(
        const string &begin_word,
        const string &end_word,
        const vector<string> &words_list) {
        const int m = begin_word.size(), n = words_list.size();
        unordered_set<string> words_set;
        for (const auto &word : words_list) {
            words_set.insert(word);
        }
        if (words_set.find(end_word) == words_set.end()) {
            return 0;
        }

        unordered_set<string> begin_set{{begin_word}};
        unordered_set<string> end_set{{end_word}};
        int step = 1;
        while (!begin_set.empty() && !end_set.empty()) {
            if (begin_set.size() > end_set.size()) {
                swap(begin_set, end_set);
            }

            unordered_set<string> next_level;
            for (auto word : begin_set) {
                for (int i = 0; i < word.size(); ++i) {
                    int letter = word[i];
                    for (char c = 'a'; c <= 'z'; ++c) {
                        word[i] = c;
                        if (end_set.find(word) != end_set.end()) {
                            return step + 1;
                        }

                        if (words_set.find(word) != words_set.end()) {
                            words_set.erase(word);
                            next_level.insert(word);
                        }
                    }

                    word[i] = letter;
                }
            }

            swap(begin_set, next_level);
            ++step;
        }

        return 0;
    }
};