Word Ladder hard

Problem Statement

Given two words, beginWord and endWord, and a word list wordList, return the length of the shortest transformation sequence from beginWord to endWord, such that:

• Only one letter can be changed at a time.
• Each transformed word must exist in the word list.

Return 0 if there is no such transformation sequence.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: hit -> hot -> dot -> dog -> cog

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: cog is not in wordList.

Steps

1. Initialization: Add beginWord to a queue q and a set visited. Initialize the transformation sequence length level to 1.

2. Breadth-First Search (BFS): While the queue is not empty, perform the following steps:

   • Dequeue a word currentWord from q.
   • Iterate through each word in wordList.
   • For each word, check if it differs from currentWord by only one letter and if it's not in visited.
   • If both conditions are true, enqueue the word to q, add it to visited, and increment level.

3. Termination: If endWord is found in visited, return level. If the queue becomes empty before finding endWord, it means there's no transformation sequence, so return 0.

Explanation

The problem is essentially finding the shortest path in a graph where words are nodes and edges exist between words that differ by one letter. Breadth-First Search (BFS) is the ideal algorithm for finding the shortest path in an unweighted graph. BFS explores the graph level by level, ensuring that the first time it finds endWord, it has found the shortest path. We use a visited set to avoid cycles and redundant exploration. The level variable keeps track of the length of the transformation sequence.

Code

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <unordered_set>

using namespace std;

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    queue<string> q;
    unordered_set<string> visited;
    q.push(beginWord);
    visited.insert(beginWord);
    int level = 1;

    unordered_set<string> wordSet;
    for (const string& word : wordList) {
        wordSet.insert(word);
    }

    if (wordSet.find(endWord) == wordSet.end()) return 0; //endWord not in wordList

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            string currentWord = q.front();
            q.pop();
            if (currentWord == endWord) return level;

            for (int j = 0; j < currentWord.length(); ++j) {
                for (char k = 'a'; k <= 'z'; ++k) {
                    string nextWord = currentWord;
                    nextWord[j] = k;
                    if (wordSet.count(nextWord) && visited.find(nextWord) == visited.end()) {
                        q.push(nextWord);
                        visited.insert(nextWord);
                    }
                }
            }
        }
        level++;
    }
    return 0;
}

int main() {
    string beginWord = "hit";
    string endWord = "cog";
    vector<string> wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
    cout << ladderLength(beginWord, endWord, wordList) << endl; // Output: 5

    beginWord = "hit";
    endWord = "cog";
    wordList = {"hot","dot","dog","lot","log"};
    cout << ladderLength(beginWord, endWord, wordList) << endl; // Output: 0

    return 0;
}

Complexity

• Time Complexity: O(M * N * 26), where M is the length of the words and N is the number of words in wordList. In the worst case, we might explore all possible one-letter changes for every word in the queue.
• Space Complexity: O(N), where N is the number of words in wordList. The space is dominated by the visited set and the queue.