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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Word Ladder

Number: 127

Difficulty: Hard

Paid? No

Companies: Amazon, Meta, LinkedIn, Google, Bloomberg, TikTok, Uber, eBay, Apple, Snap, Adobe, The Trade Desk, Reddit, Visa, Microsoft, Walmart Labs, Samsung, Box, Salesforce, PhonePe, Yelp

Problem Description

Given a start word (beginWord), a target word (endWord), and a list of allowed words (wordList), determine the minimum number of steps required to transform beginWord into endWord. Each step must change exactly one letter and the resulting word must be in wordList. If the transformation is impossible, return 0.

Key Insights

  • Use Breadth-First Search (BFS) to explore transformations level by level to guarantee the shortest path.
  • Preprocess words by generating intermediate representations (e.g., replacing each letter with a wildcard) to quickly find neighbors.
  • Use a visited set to avoid cycles.
  • Each transformation counts as a level in the BFS, so the answer is the number of levels traversed.

Space and Time Complexity

Time Complexity: O(N * M^2) where N is the number of words and M is the length of each word.
Space Complexity: O(N * M) for the storage of intermediate mappings and the BFS queue.

Solution

We solve the problem using a BFS approach. First, we preprocess the wordList by creating a mapping of all possible intermediate states. For example, for the word "dog" and wildcard position, we generate "og", "dg", and "do*". This helps us find all adjacent words (neighbors) that are only one letter different in constant time. We then initialize a queue with the beginWord and initiate the BFS. For each word dequeued, we explore all valid transformations using the precomputed intermediate mapping. If the endWord is reached during this process, we return the current level (transformation sequence length). Otherwise, we continue the BFS until all possibilities are exhausted. If no valid transformation sequence is found, we return 0.

Code Solutions

# Python solution using BFS

from collections import defaultdict, deque

def ladderLength(beginWord, endWord, wordList):
    # Create a set for fast lookup
    wordSet = set(wordList)
    if endWord not in wordSet:
        return 0

    # Preprocessing: build a dictionary of intermediate states to words
    L = len(beginWord)
    all_combo_dict = defaultdict(list)
    for word in wordSet:
        for i in range(L):
            # Key with a wildcard at the i-th position
            intermediate = word[:i] + '*' + word[i+1:]
            all_combo_dict[intermediate].append(word)
    
    # Initialize BFS
    queue = deque([(beginWord, 1)])
    visited = set([beginWord])
    
    while queue:
        current_word, level = queue.popleft()
        for i in range(L):
            intermediate = current_word[:i] + '*' + current_word[i+1:]
            # Check all words sharing the same intermediate state
            for word in all_combo_dict[intermediate]:
                if word == endWord:
                    return level + 1
                if word not in visited:
                    visited.add(word)
                    queue.append((word, level + 1))
            # Once processed, clear the intermediate state list to save processing time
            all_combo_dict[intermediate] = []
    return 0

# Example usage:
# print(ladderLength("hit", "cog", ["hot","dot","dog","lot","log","cog"]))
← Back to All Questions