Word Ladder 🧠

LeetCode Link: Word Ladder

Difficulty: Hard

Problem Explanation 📝

Problem: LeetCode 127 - Word Ladder

Description: Given two words, beginWord and endWord, and a dictionary 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 wordList.

If there is no such transformation sequence, return 0.

Intuition: This problem can be solved using a graph traversal algorithm such as breadth-first search (BFS). We can treat each word as a node in the graph and connect the words that differ by a single character. The problem then reduces to finding the shortest path from the beginWord to the endWord.

Approach:

1. Build a set from the wordList for efficient lookup.
2. Create a queue for BFS traversal and initialize it with the beginWord.
3. Initialize a distance variable to track the length of the transformation sequence.
4. Perform BFS:

• Pop the front word from the queue.
• For each character position in the word, replace it with each of the 26 alphabets and check if the resulting word is in the wordList.
• If the resulting word is the endWord, return the current distance + 1.
• If the resulting word is in the wordList, add it to the queue and remove it from the wordList to avoid revisiting.

5. If no transformation sequence is found, return 0.

⌛ Time Complexity: The time complexity is O(N * M^2), where N is the number of words in the wordList and M is the length of the words. In the worst case, we may need to explore all possible transformations of each word.

💾 Space Complexity: The space complexity is O(N * M^2), where N is the number of words in the wordList and M is the length of the words. This is the space used for the wordList set, queue, and visited set.

Solutions 💡

Cpp 💻

class Solution {
  public:
    int ladderLength(string beginWord, string endWord, vector<string> &wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());  // Convert wordList to a set for efficient lookup

        if (wordSet.find(endWord) == wordSet.end()) {
            return 0;  // endWord is not in the wordList, no transformation sequence possible
        }

        queue<string> q;
        q.push(beginWord);
        int distance = 1;

        while (!q.empty()) {
            int levelSize = q.size();

            for (int i = 0; i < levelSize; ++i) {
                string currentWord = q.front();
                q.pop();

                // Check each character position of the word and replace it with all possible alphabets
                for (int j = 0; j < currentWord.length(); ++j) {
                    char originalChar = currentWord[j];

                    for (char c = 'a'; c <= 'z'; ++c) {
                        currentWord[j] = c;

                        if (currentWord == endWord) {
                            return distance + 1;  // Transformation sequence found, return the distance
                        }

                        if (wordSet.find(currentWord) != wordSet.end()) {
                            q.push(currentWord);  // Add the transformed word to the queue
                            wordSet.erase(currentWord);  // Remove the transformed word from the wordSet
                        }
                    }

                    currentWord[j] = originalChar;  // Revert back the character
                }
            }

            ++distance;  // Increment the distance for each level of BFS traversal
        }

        return 0;  // No transformation sequence found
    }
};

// Bidirectional BFS
/*
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end()); // Convert wordList to a set for efficient lookup

        if (wordSet.find(endWord) == wordSet.end()) {
            return 0; // endWord is not in the wordList, no transformation sequence possible
        }

        unordered_set<string> beginSet, endSet; // Sets for the current level of traversal from the beginWord and endWord
        beginSet.insert(beginWord);
        endSet.insert(endWord);

        int distance = 1; // Distance between beginWord and endWord

        while (!beginSet.empty() && !endSet.empty()) {
            // Always expand the smaller set to reduce the search space
            if (beginSet.size() > endSet.size()) {
                swap(beginSet, endSet);
            }

            unordered_set<string> temp; // Temporary set to store the next level of words

            for (const string& word : beginSet) {
                string currentWord = word;

                // Check each character position of the word and replace it with all possible alphabets
                for (int i = 0; i < currentWord.length(); ++i) {
                    char originalChar = currentWord[i];

                    for (char c = 'a'; c <= 'z'; ++c) {
                        currentWord[i] = c;

                        if (endSet.find(currentWord) != endSet.end()) {
                            return distance + 1; // Transformation sequence found, return the distance
                        }

                        if (wordSet.find(currentWord) != wordSet.end()) {
                            temp.insert(currentWord); // Add the transformed word to the next level set
                            wordSet.erase(currentWord); // Remove the transformed word from the wordSet
                        }
                    }

                    currentWord[i] = originalChar; // Revert back the character
                }
            }

            swap(beginSet, temp); // Update the current level set with the next level set
            ++distance; // Increment the distance for each level of BFS traversal
        }

        return 0; // No transformation sequence found
    }
};
*/

Python 🐍

from collections import deque


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordSet = set(wordList)
        if endWord not in wordSet:
            return 0

        queue = deque([(beginWord, 1)])  # Start from the beginWord with level 1
        visited = set()

        while queue:
            word, level = queue.popleft()
            if word == endWord:
                return level

            for i in range(len(word)):
                for c in "abcdefghijklmnopqrstuvwxyz":
                    new_word = word[:i] + c + word[i + 1 :]
                    if new_word in wordSet and new_word not in visited:
                        visited.add(new_word)
                        queue.append((new_word, level + 1))

        return 0