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 -> s1 -> s2 -> … -> sk such that:

Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList. sk == 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 && Breadth-First Search

m = wordList[i].size(), n = wordList.size()
Time complexity: O($m^2$n)
Space complexity: O($m^2$n)

class Solution {
public:
    int ladderLength(
        const string &beginWord,
        const string &endWord,
        const vector<string> &wordList) {
        unordered_map<string, unordered_set<string>> fake_neighbors;
        bool have_end = false;
        for (const auto &word : wordList) {
            if (word == endWord) {
                have_end = true;
            }

            string fake_neightbor = word;
            for (int i = 0; i < word.size(); ++i) {
                char letter = fake_neightbor[i];
                fake_neightbor[i] = '*';
                fake_neighbors[fake_neightbor].insert(word);
                fake_neightbor[i] = letter;
            }
        }

        if (!have_end) {
            return 0;
        }

        int path = 1;
        queue<string> current_words({beginWord}), neighbor_words;
        for (; !current_words.empty(); ++path) {
            while (!current_words.empty()) {
                auto current_word = current_words.front();
                current_words.pop();

                string fake_neightbor = current_word;
                for (int i = 0; i < current_word.size(); ++i) {
                    char letter = fake_neightbor[i];
                    fake_neightbor[i] = '*';
                    fake_neighbors[fake_neightbor].erase(current_word);
                    for (auto word : fake_neighbors[fake_neightbor]) {
                        if (word == endWord) {
                            return path + 1;
                        }

                        neighbor_words.push(word);
                    }

                    fake_neighbors.erase(fake_neightbor);
                    fake_neightbor[i] = letter;
                }
            }

            swap(current_words, neighbor_words);
        }

        return 0;
    }
};