Word Ladder

Problem

You are given two words, beginWord and endWord, and also a list of words wordList. All of the given words are of the same length, consisting of lowercase English letters, and are all distinct.

Your goal is to transform beginWord into endWord by following the rules:

• You may transform beginWord to any word within wordList, provided that at exactly one position the words have a different character, and the rest of the positions have the same characters.
• You may repeat the previous step with the new word that you obtain, and you may do this as many times as needed.

Return the minimum number of words within the transformation sequence needed to obtain the endWord, or 0 if no such sequence exists.

Examples

Example 1:

Input: beginWord = "cat", endWord = "sag", wordList = ["bat","bag","sag","dag","dot"]

Output: 4

Explanation: The transformation sequence is "cat" -> "bat" -> "bag" -> "sag".

Example 2:

Input: beginWord = "cat", endWord = "sag", wordList = ["bat","bag","sat","dag","dot"]

Output: 0

Explanation: There is no possible transformation sequence from "cat" to "sag" since the word "sag" is not in the wordList.

Constraints

• 1 <= beginWord.length <= 10
• 1 <= wordList.length <= 100

You should aim for a solution with O((m ^ 2) * n) time and O((m ^ 2) * n) space, where n is the number of words and m is the length of the word.

Solution

BFS since each step is a word transition. Generate children if word distance is 1.

class Solution {
    struct Node {
        std::string state;
        int g;
    };
 
    int word_distance(const std::string &s1, const std::string &s2) {
        int count = 0;
        for (int i = 0; i < std::min(s1.size(), s2.size()); ++i) {
            count += (s1[i] != s2[i]) ? 1 : 0;
        }
        return count;
    }
 
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        std::queue<Node> open;
        std::unordered_set<std::string> closed;
 
        open.emplace(beginWord, 1);
        closed.insert(beginWord);
 
        while (!open.empty()) {
            Node current = std::move(open.front());
            open.pop();
            // Solution check
            if (current.state == endWord) {
                return current.g;
            }
            // Generate children
            for (const auto &word : wordList) {
                if (closed.contains(word)) { continue; }
                if (word_distance(word, current.state) == 1) {
                    open.emplace(word, current.g + 1);
                    closed.insert(word);
                }
            }
        }
        return 0;
    }
};