LeetCode Solutions Blog

Word Ladder II

Difficulty: Hard

Problem Description

Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord such that every adjacent pair of words differs by a single letter, and every intermediate word must be in wordList. If no such sequence exists, return an empty list.

Key Insights

The problem can be solved using a breadth-first search (BFS) to find the shortest paths.
We need to explore all possible transformations of words and track the paths taken.
A backtracking approach is used to reconstruct the paths once the shortest length is found.
A hash map can be used to store the adjacency list of words that can be transformed into each other.

Space and Time Complexity

Time Complexity: O(N * 26^L), where N is the number of words in the wordList and L is the length of the words.
Space Complexity: O(N), for storing the adjacency list and the result paths.

Solution

This problem can be approached using a breadth-first search (BFS) to find the shortest paths from beginWord to endWord. We construct an adjacency list to represent all possible transformations, where each word is connected to other words that differ by one letter. After finding the shortest transformation length, we can use backtracking to reconstruct all valid transformation sequences.

Code Solutions

from collections import defaultdict, deque

def findLadders(beginWord, endWord, wordList):
    wordSet = set(wordList)
    if endWord not in wordSet:
        return []

    # Step 1: Build the adjacency list
    neighbors = defaultdict(list)
    for word in wordSet:
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                newWord = word[:i] + c + word[i+1:]
                if newWord in wordSet and newWord != word:
                    neighbors[word].append(newWord)

    # Step 2: BFS to find the shortest path length
    queue = deque([beginWord])
    visited = {beginWord: 1}  # Tracks the distance from beginWord
    found = False
    while queue and not found:
        for _ in range(len(queue)):
            current = queue.popleft()
            for neighbor in neighbors[current]:
                if neighbor not in visited:
                    visited[neighbor] = visited[current] + 1
                    queue.append(neighbor)
                    if neighbor == endWord:
                        found = True

    # If endWord was not reached
    if endWord not in visited:
        return []

    # Step 3: Backtrack to find all paths
    def backtrack(word):
        if word == beginWord:
            return [[beginWord]]
        paths = []
        for neighbor in neighbors[word]:
            if visited[neighbor] == visited[word] - 1:
                for path in backtrack(neighbor):
                    paths.append(path + [word])
        return paths

    return backtrack(endWord)

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