LeetCode Solutions Blog

Word Ladder II

Number: 126

Difficulty: Hard

Paid? No

Problem Description

Given two words, beginWord and endWord, and a wordList, the goal is to find all the shortest transformation sequences from beginWord to endWord. A transformation sequence is a list of words where every adjacent pair of words differs by one letter and each intermediate word exists in wordList. If no valid sequence exists (for example, if endWord is not in wordList), return an empty list.

Key Insights

Use Breadth-First Search (BFS) to traverse level-by-level and capture only the shortest paths.
Build a parent mapping during BFS to record which words lead to each newly discovered word.
Once the shortest path is found via BFS, use backtracking (or DFS) from endWord to reconstruct all transformation sequences.
Remove words as they are visited within a level to avoid unnecessary revisits and cycles.
The solution must handle multiple shortest paths, so maintaining a list of predecessors for each word is crucial.

Space and Time Complexity

Time Complexity: O(N * L * 26) where N is the number of words in the wordList and L is the length of each word. This accounts for checking all possible one-letter transformations. Space Complexity: O(N * L) for storing the parent mapping and maintaining the BFS queue and other auxiliary data structures.

Solution

We solve the problem in two major phases:

Use BFS to explore from beginWord to endWord. During BFS, record all parents for each word encountered. This ensures we capture all possible predecessors that yield a shortest transformation.
Once the BFS completes (once endWord is reached), use backtracking (DFS) beginning from the endWord and moving backwards via the parent mapping to reconstruct all transformation sequences in reverse. Finally, reverse each sequence to present it from beginWord to endWord.

This two-phase approach guarantees that only the shortest paths are reconstructed, as BFS ensures level-by-level exploration.

Code Solutions

# Python solution for Word Ladder II

from collections import defaultdict, deque

def findLadders(beginWord, endWord, wordList):
    # Convert list to set for fast lookup
    wordSet = set(wordList)
    if endWord not in wordSet:
        return []
    
    # Dictionary to hold parent pointers for backtracking: child -> list of parents
    parents = defaultdict(list)
    # Set for words visited at current BFS level
    level = {beginWord}
    # Flag to stop BFS when endWord is reached
    found = False
    
    while level and not found:
        next_level = set()
        # Remove words of current level from wordSet to prevent cycles
        wordSet -= level
        for word in level:
            # Try all possible one-letter transformations
            for i in range(len(word)):
                for char in 'abcdefghijklmnopqrstuvwxyz':
                    candidate = word[:i] + char + word[i+1:]
                    if candidate in wordSet:
                        # If candidate is the endWord, note that we have found a path
                        if candidate == endWord:
                            found = True
                        # Record the current word as a parent of candidate word
                        parents[candidate].append(word)
                        next_level.add(candidate)
        # Move to the next level of the BFS
        level = next_level

    # The result list to hold all valid transformation sequences
    res = []
    
    # Helper function to backtrack from endWord to beginWord using the parents dictionary
    def backtrack(word, path):
        if word == beginWord:
            # Append reversed path to have the sequence from beginWord to endWord
            res.append(path[::-1])
            return
        # Recurse over all parents of the current word
        for parent in parents[word]:
            backtrack(parent, path + [parent])
    
    if found:
        backtrack(endWord, [endWord])
    return res

# Example usage:
# print(findLadders("hit", "cog", ["hot","dot","dog","lot","log","cog"]))