Leetcode 126. Word Ladder II

Let's understand what we're being asked to do. We have a beginWord like 'hit', an endWord like 'cog', and a wordList like ['hot','dot','dog','lot','log','cog']. We need to find all shortest transformation sequences from 'hit' to 'cog'.

A transformation means changing exactly one letter at a time, and each intermediate word must exist in the wordList. For example: 'hit' -> 'hot' -> 'dot' -> 'dog' -> 'cog' is valid (each step changes one letter).

Important constraint: We want ALL shortest paths, not just one! If there are multiple ways to reach endWord in the minimum number of steps, we need to return all of them.

Key insight: Words are like nodes in a graph, and edges connect words that differ by exactly one letter. The problem becomes: find all shortest paths in an unweighted graph.

Edge cases to consider: What if endWord is not in wordList? (return empty list). What if no transformation sequence exists? What if beginWord equals endWord?

The brute force approach uses pure DFS to explore all possible transformation paths from beginWord to endWord. Starting from beginWord, recursively try transforming to every word in wordList that differs by one letter, marking words as visited to avoid cycles. When endWord is reached, record the path. After exploring all paths, filter to keep only the shortest ones. This approach explores many unnecessary longer paths before finding the optimal length.

def word_ladder(begin_word, end_word, word_list):
    """
    Find all shortest transformation sequences from begin_word to end_word.
    Brute force: Use DFS to explore all paths, then filter shortest ones.
    """
    # Convert word list to set for O(1) lookup
    word_set = set(word_list)
    
    # If end_word not in word_list, no solution
    if end_word not in word_set:
        return []
    
    # Helper function to check if two words differ by exactly one letter
    def one_letter_diff(word1, word2):
        if len(word1) != len(word2):
            return False
        diff_count = 0
        for i in range(len(word1)):
            if word1[i] != word2[i]:
                diff_count += 1
                if diff_count > 1:
                    return False
        return diff_count == 1
    
    # Store all paths found
    all_paths = []
    
    # DFS to explore all transformation paths
    def dfs(current_word, path, visited):
        # Base case: reached end_word
        if current_word == end_word:
            all_paths.append(path.copy())
            return
        
        # Try transforming to every word in word_list
        for word in word_set:
            # Skip if already visited (avoid cycles)
            if word in visited:
                continue
            
            # Check if word differs by exactly one letter
            if one_letter_diff(current_word, word):
                # Mark as visited
                visited.add(word)
                path.append(word)
                
                # Recursively explore from this word
                dfs(word, path, visited)
                
                # Backtrack: unmark and remove from path
                path.pop()
                visited.remove(word)
    
    # Start DFS from begin_word
    initial_visited = {begin_word}
    initial_path = [begin_word]
    dfs(begin_word, initial_path, initial_visited)
    
    # Filter to keep only shortest paths
    if not all_paths:
        return []
    
    min_length = min(len(path) for path in all_paths)
    shortest_paths = [path for path in all_paths if len(path) == min_length]
    
    return shortest_paths

In an unweighted graph, BFS discovers nodes level by level, guaranteeing that the first time we reach a node, we've found the shortest distance to it.

Once we know the shortest distance to each word, we can work backwards from endWord to beginWord, only following edges that decrease the distance by 1. This ensures we only traverse shortest paths.

A naive DFS approach would explore all possible paths, including many longer-than-optimal ones, leading to exponential time complexity.

By using BFS first to build a distance map, then DFS to enumerate only shortest paths, we avoid exploring any path that's longer than necessary. This two-phase approach (BFS + DFS) is much more efficient.

Think of this like finding all shortest routes between two cities on a map:

Phase 1 (BFS): Measure the shortest distance from the start city to every other city. Mark each city with its distance number.

Phase 2 (DFS/Backtracking): Starting from the destination, work backwards. At each step, only move to cities whose distance number is exactly 1 less than your current city. This guarantees you're always on a shortest path.

The level-by-level exploration of BFS is what makes this work - it's like ripples spreading outward from a stone dropped in water.

The optimal approach uses a two-phase strategy: First, run BFS from beginWord to build a distance map showing the shortest distance to each word. This creates a level graph where each word knows its distance from the start. Second, use DFS/backtracking starting from endWord, working backwards to beginWord. At each step, only follow edges to words whose distance is exactly 1 less, ensuring we only traverse shortest paths. This guarantees we enumerate all shortest transformation sequences without exploring longer paths.

from collections import deque, defaultdict
def find_ladders(begin_word, end_word, word_list):
    """
    Find all shortest transformation sequences from begin_word to end_word.
    Uses BFS to build distance map, then DFS to enumerate all shortest paths.
    """
    # Convert word_list to set for O(1) lookup
    word_set = set(word_list)
    
    # If end_word not in word_list, no transformation possible
    if end_word not in word_set:
        return []
    
    # BFS Phase: Build distance map showing shortest distance from begin_word
    queue = deque([begin_word])
    distances = {begin_word: 0}
    
    while queue:
        current_word = queue.popleft()
        current_distance = distances[current_word]
        
        # Try all one-letter transformations
        for i in range(len(current_word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                if c == current_word[i]:
                    continue
                
                # Generate neighbor word
                neighbor = current_word[:i] + c + current_word[i+1:]
                
                # If neighbor is in word_set and not visited
                if neighbor in word_set and neighbor not in distances:
                    distances[neighbor] = current_distance + 1
                    queue.append(neighbor)
    
    # If end_word not reached, return empty list
    if end_word not in distances:
        return []
    
    # DFS Phase: Backtrack from end_word to begin_word using distance map
    all_paths = []
    current_path = [end_word]
    
    def backtrack(word, path):
        # Base case: reached begin_word
        if word == begin_word:
            all_paths.append(path[::-1])
            return
        
        # Try all one-letter transformations
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                if c == word[i]:
                    continue
                
                # Generate neighbor word
                neighbor = word[:i] + c + word[i+1:]
                
                # Only follow edges to words with distance exactly 1 less
                if neighbor in distances and distances[neighbor] == distances[word] - 1:
                    path.append(neighbor)
                    backtrack(neighbor, path)
                    path.pop()
    
    backtrack(end_word, current_path)
    return all_paths

• BFS for shortest path discovery + DFS for path enumeration: When you need to find ALL shortest paths (not just one), use BFS first to build a level/distance map from the target, then backtrack with DFS using only edges that decrease distance by 1 - this two-phase approach guarantees you only explore shortest paths without redundant work.
• Bidirectional BFS optimization: Build the graph structure using BFS from endWord backwards to compute distances to all reachable words - this prunes the search space early by identifying which words can actually reach the target, avoiding exploration of dead-end branches during path reconstruction.
• Level-based graph construction: Treat the word transformation as an unweighted graph where BFS naturally discovers shortest distances - store each word's distance/level from the target, then during DFS only follow edges to words at level-1, ensuring all reconstructed paths have identical optimal length.
• Neighbor generation vs pre-built adjacency list: For word ladder problems, generating neighbors on-the-fly (try all 26 letters at each position and check wordList membership with a Set) is often faster than pre-computing all edges, especially when the word list is large but words are short - O(26*L) per word beats O(N²*L) preprocessing.
• Backtracking with distance constraints: The critical insight is using the distance map as a filter during DFS - only recurse into neighbors whose distance is exactly one less than current word's distance, which prevents cycles and ensures you're always moving toward the source along a shortest path.
• Graph problems with path enumeration: This pattern applies broadly to any problem requiring all optimal solutions in a graph - use BFS/Dijkstra to find optimal distances first, then use constrained DFS/backtracking with the distance map to enumerate only optimal paths (useful in routing, dependency resolution, and game state exploration).