Word Ladder - Leetcode Solution

The Word Ladder problem on LeetCode requires you to find the shortest path from a given start word to a given end word by changing one letter at a time, such that every intermediate word is also a valid word from a given word list.

A valid word list is provided as input, and the start and end words are also given. Your task is to determine the number of steps required to reach the end word from the start word, where each step involves changing one letter at a time.

To solve this problem, we can follow these steps:

1. Initialize a queue that will store our intermediate words.

2. Add the start word to the queue.

3. Initialize a visited set to keep track of the words we have already visited.

4. Add the start word to the visited set.

5. Initialize a step count to keep track of the number of steps required to reach the end word.

6. While the queue is not empty, do the following:

   • Remove the first word from the queue.
   • For each character in the word, replace it with a different letter of the alphabet, and check if the resulting word is in the word list and not in the visited set.
   • If the resulting word is the end word, return the current step count + 1.
   • If the resulting word is valid, add it to the queue and the visited set.
   • Repeat this process until the queue is empty.

7. If we reach the end word without finding it, return 0.

Here is the Python code that implements this solution:

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)])
        visited = set()
        
        while queue:
            word, step = queue.popleft()
            
            if word == endWord:
                return step
            
            for i in range(len(word)):
                for c in "abcdefghijklmnopqrstuvwxyz":
                    newWord = word[:i] + c + word[i+1:]
                    if newWord in wordSet and newWord not in visited:
                        queue.append((newWord, step+1))
                        visited.add(newWord)
                        
        return 0

The time complexity of this solution is O(M^2 * N), where M is the length of the words and N is the size of the word list. The space complexity of this solution is also O(M^2 * N) due to the use of the queue and visited set.

1