We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Word Ladder

Difficulty: Hard

Problem 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.

Key Insights

  • Each word can be transformed into others by changing one letter at a time.
  • A breadth-first search (BFS) is suitable for exploring all possible transformations level by level.
  • The problem can be represented as a graph where each word is a node and edges exist between nodes that differ by one letter.
  • Using a set for the wordList allows for O(1) average-time complexity for lookups.

Space and Time Complexity

Time Complexity: O(N * M), where N is the number of words in wordList and M is the length of each word (since we check all possible single-letter transformations for each word).

Space Complexity: O(N), for storing the visited words and the queue used in BFS.

Solution

The solution uses a breadth-first search (BFS) algorithm to explore the transformation sequences. We start from the beginWord and explore all possible transformations that lead to words in the wordList. Each valid transformation is added to a queue, and we keep track of the number of transformations taken to reach each word. The BFS continues until we either find the endWord or exhaust all possibilities.

  1. Initialize a queue and add the beginWord with a step count of 1.
  2. Use a set to store the wordList for O(1) lookups.
  3. For each word dequeued, generate all possible transformations by changing each letter to every other letter from 'a' to 'z'.
  4. If a transformation results in a word that is in the wordList, enqueue it with an incremented step count and mark it as visited.
  5. If we dequeue the endWord, return the step count.
  6. If the queue is exhausted without finding the endWord, return 0.

Code Solutions

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    wordSet = set(wordList)
    if endWord not in wordSet:
        return 0
    
    queue = deque([(beginWord, 1)])  # (current word, current length)
    while queue:
        current_word, length = queue.popleft()
        
        if current_word == endWord:
            return length
        
        for i in range(len(current_word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = current_word[:i] + c + current_word[i+1:]
                if next_word in wordSet:
                    queue.append((next_word, length + 1))
                    wordSet.remove(next_word)  # Mark as visited
                    
    return 0
← Back to All Questions