Word Ladder

Find the shortest transformation sequence from beginWord to endWord using single character changes

Language Selection

Choose your preferred programming language

Showing: Python

Word Ladder

Problem Statement

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.

Input/Output Specifications

  • Input:
    • beginWord: Starting word for the transformation
    • endWord: Target word for the transformation
    • wordList: List of valid intermediate words
  • Output: Length of shortest transformation sequence, or 0 if impossible
  • Constraints:
    • 1 <= beginWord.length <= 10
    • endWord.length == beginWord.length
    • 1 <= wordList.length <= 5000
    • wordList[i].length == beginWord.length
    • All words consist of lowercase English letters
    • All words in wordList are unique
    • beginWord != endWord

Examples

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog", which is 5 words long.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Example 3:

Input: beginWord = "a", endWord = "c", wordList = ["a","b","c"]
Output: 3
Explanation: The transformation sequence is "a" -> "b" -> "c".

Example 4:

Input: beginWord = "game", endWord = "maze", wordList = ["came","name","game","maze"]
Output: 4
Explanation: "game" -> "came" -> "name" -> "maze"

Solution Approaches

Approach 1: BFS with Adjacent Word Generation (Optimal)

Use breadth-first search to find the shortest path by generating adjacent words at each step.

Algorithm Explanation

  1. Input Validation: Check if endWord exists in wordList
  2. BFS Setup: Initialize queue with beginWord and visited set
  3. Level Processing: For each level of BFS:
    • Generate all possible adjacent words (change each character)
    • Check if adjacent word is in wordList and not visited
    • If adjacent word is endWord, return current level + 1
    • Add valid adjacent words to queue for next level
  4. Result: Return 0 if no path found

Implementation

Python:

from collections import deque

class Solution:
    """
    BFS approach for word ladder shortest path
    Time: O(M² × N) where M is word length, N is wordList size
    Space: O(M × N) for queue and visited set
    """
    
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        if endWord not in wordList:
            return 0
        
        wordSet = set(wordList)
        queue = deque([beginWord])
        visited = {beginWord}
        level = 1
        
        while queue:
            for _ in range(len(queue)):
                current_word = queue.popleft()
                
                # Generate all possible adjacent words
                for i in range(len(current_word)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        if c != current_word[i]:
                            adjacent_word = current_word[:i] + c + current_word[i+1:]
                            
                            if adjacent_word == endWord:
                                return level + 1
                            
                            if adjacent_word in wordSet and adjacent_word not in visited:
                                visited.add(adjacent_word)
                                queue.append(adjacent_word)
            
            level += 1
        
        return 0

Java:

class Solution {
    /**
     * BFS approach for word ladder shortest path
     * Time: O(M² × N) where M is word length, N is wordList size
     * Space: O(M × N) for queue and visited set
     */
    
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) {
            return 0;
        }
        
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        queue.offer(beginWord);
        visited.add(beginWord);
        int level = 1;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                String currentWord = queue.poll();
                
                // Generate all possible adjacent words
                for (int j = 0; j < currentWord.length(); j++) {
                    char[] chars = currentWord.toCharArray();
                    
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c != chars[j]) {
                            chars[j] = c;
                            String adjacentWord = new String(chars);
                            
                            if (adjacentWord.equals(endWord)) {
                                return level + 1;
                            }
                            
                            if (wordSet.contains(adjacentWord) && !visited.contains(adjacentWord)) {
                                visited.add(adjacentWord);
                                queue.offer(adjacentWord);
                            }
                        }
                    }
                }
            }
            
            level++;
        }
        
        return 0;
    }
}

Go:

// ladderLength - BFS approach for word ladder shortest path
// Time: O(M² × N) where M is word length, N is wordList size
// Space: O(M × N) for queue and visited set
func ladderLength(beginWord string, endWord string, wordList []string) int {
    // Convert wordList to set for O(1) lookup
    wordSet := make(map[string]bool)
    for _, word := range wordList {
        wordSet[word] = true
    }
    
    if !wordSet[endWord] {
        return 0
    }
    
    queue := []string{beginWord}
    visited := make(map[string]bool)
    visited[beginWord] = true
    level := 1
    
    for len(queue) > 0 {
        size := len(queue)
        
        for i := 0; i < size; i++ {
            currentWord := queue[0]
            queue = queue[1:]
            
            // Generate all possible adjacent words
            for j := 0; j < len(currentWord); j++ {
                for c := 'a'; c <= 'z'; c++ {
                    if rune(currentWord[j]) != c {
                        adjacentWord := currentWord[:j] + string(c) + currentWord[j+1:]
                        
                        if adjacentWord == endWord {
                            return level + 1
                        }
                        
                        if wordSet[adjacentWord] && !visited[adjacentWord] {
                            visited[adjacentWord] = true
                            queue = append(queue, adjacentWord)
                        }
                    }
                }
            }
        }
        
        level++
    }
    
    return 0
}

JavaScript:

/**
 * BFS approach for word ladder shortest path
 * Time: O(M² × N) where M is word length, N is wordList size
 * Space: O(M × N) for queue and visited set
 */
function ladderLength(beginWord, endWord, wordList) {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) {
        return 0;
    }
    
    const queue = [beginWord];
    const visited = new Set([beginWord]);
    let level = 1;
    
    while (queue.length > 0) {
        const size = queue.length;
        
        for (let i = 0; i < size; i++) {
            const currentWord = queue.shift();
            
            // Generate all possible adjacent words
            for (let j = 0; j < currentWord.length; j++) {
                for (let c = 97; c <= 122; c++) { // 'a' to 'z'
                    const char = String.fromCharCode(c);
                    if (char !== currentWord[j]) {
                        const adjacentWord = currentWord.slice(0, j) + char + currentWord.slice(j + 1);
                        
                        if (adjacentWord === endWord) {
                            return level + 1;
                        }
                        
                        if (wordSet.has(adjacentWord) && !visited.has(adjacentWord)) {
                            visited.add(adjacentWord);
                            queue.push(adjacentWord);
                        }
                    }
                }
            }
        }
        
        level++;
    }
    
    return 0;
}

C#:

public class Solution {
    /// <summary>
    /// BFS approach for word ladder shortest path
    /// Time: O(M² × N) where M is word length, N is wordList size
    /// Space: O(M × N) for queue and visited set
    /// </summary>
    
    public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
        var wordSet = new HashSet<string>(wordList);
        if (!wordSet.Contains(endWord)) {
            return 0;
        }
        
        var queue = new Queue<string>();
        var visited = new HashSet<string>();
        
        queue.Enqueue(beginWord);
        visited.Add(beginWord);
        int level = 1;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            
            for (int i = 0; i < size; i++) {
                string currentWord = queue.Dequeue();
                
                // Generate all possible adjacent words
                for (int j = 0; j < currentWord.Length; j++) {
                    char[] chars = currentWord.ToCharArray();
                    
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c != chars[j]) {
                            chars[j] = c;
                            string adjacentWord = new string(chars);
                            
                            if (adjacentWord == endWord) {
                                return level + 1;
                            }
                            
                            if (wordSet.Contains(adjacentWord) && !visited.Contains(adjacentWord)) {
                                visited.Add(adjacentWord);
                                queue.Enqueue(adjacentWord);
                            }
                        }
                    }
                }
            }
            
            level++;
        }
        
        return 0;
    }
}

Approach 2: Bidirectional BFS (Optimized)

Use bidirectional BFS to search from both beginWord and endWord simultaneously.

Algorithm Explanation

  1. Two-way Search: Start BFS from both beginWord and endWord
  2. Alternating Expansion: Expand the smaller frontier at each step
  3. Intersection Detection: When frontiers meet, path is found
  4. Optimization: Reduces search space significantly

Implementation

Python:

class Solution:
    """
    Bidirectional BFS for word ladder (optimized)
    Time: O(M² × N/2) average case improvement
    Space: O(M × N) for sets and queues
    """
    
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        if endWord not in wordList:
            return 0
        
        wordSet = set(wordList)
        
        # Two sets for bidirectional search
        begin_set = {beginWord}
        end_set = {endWord}
        visited = set()
        level = 1
        
        while begin_set and end_set:
            # Always expand the smaller set
            if len(begin_set) > len(end_set):
                begin_set, end_set = end_set, begin_set
            
            next_set = set()
            
            for word in begin_set:
                for i in range(len(word)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        if c != word[i]:
                            adjacent_word = word[:i] + c + word[i+1:]
                            
                            if adjacent_word in end_set:
                                return level + 1
                            
                            if adjacent_word in wordSet and adjacent_word not in visited:
                                visited.add(adjacent_word)
                                next_set.add(adjacent_word)
            
            begin_set = next_set
            level += 1
        
        return 0

Approach 3: Graph Building + BFS

Pre-build the graph of adjacent words, then run BFS.

Python:

from collections import defaultdict, deque

class Solution:
    """
    Graph building + BFS approach
    Time: O(M² × N) for building graph + O(N) for BFS
    Space: O(M² × N) for adjacency list
    """
    
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        if endWord not in wordList:
            return 0
        
        # Add beginWord to wordList if not present
        if beginWord not in wordList:
            wordList.append(beginWord)
        
        # Build adjacency list using patterns
        neighbors = defaultdict(list)
        for word in wordList:
            for i in range(len(word)):
                pattern = word[:i] + "*" + word[i+1:]
                neighbors[pattern].append(word)
        
        # BFS
        queue = deque([beginWord])
        visited = {beginWord}
        level = 1
        
        while queue:
            for _ in range(len(queue)):
                word = queue.popleft()
                
                for i in range(len(word)):
                    pattern = word[:i] + "*" + word[i+1:]
                    
                    for neighbor in neighbors[pattern]:
                        if neighbor == endWord:
                            return level + 1
                        
                        if neighbor not in visited:
                            visited.add(neighbor)
                            queue.append(neighbor)
            
            level += 1
        
        return 0

Complexity Analysis

BFS Approach

  • Time Complexity: O(M² × N) where M is word length and N is wordList size
  • Space Complexity: O(M × N) for queue and visited set

Bidirectional BFS

  • Time Complexity: O(M² × N) worst case, but significantly faster in practice
  • Space Complexity: O(M × N) for sets and visited tracking

Graph Building + BFS

  • Time Complexity: O(M² × N) for building + O(N + E) for BFS
  • Space Complexity: O(M² × N) for adjacency list

Key Insights

  1. Shortest Path Problem: Use BFS for unweighted shortest path
  2. State Space: Each word is a state, edges connect words differing by one character
  3. Level-by-Level: BFS naturally gives shortest transformation sequence
  4. Optimization: Bidirectional search can halve the search space

Edge Cases

  1. EndWord Not in WordList: Return 0 immediately
  2. No Transformation Possible: Isolated components in word graph
  3. BeginWord equals EndWord: Should return 1 (though problem states they’re different)
  4. Single Character Words: Simple case with direct character substitution
  5. Large Word Length: Performance considerations for character generation

Test Cases

# Test cases for validation
def test_word_ladder():
    solution = Solution()
    
    # Test case 1: Basic example
    assert solution.ladderLength("hit", "cog", ["hot","dot","dog","lot","log","cog"]) == 5
    
    # Test case 2: EndWord not in wordList
    assert solution.ladderLength("hit", "cog", ["hot","dot","dog","lot","log"]) == 0
    
    # Test case 3: Simple transformation
    assert solution.ladderLength("a", "c", ["a","b","c"]) == 3
    
    # Test case 4: Direct transformation
    assert solution.ladderLength("hot", "dog", ["hot","dog"]) == 0
    
    # Test case 5: No path exists
    assert solution.ladderLength("hit", "cog", ["hot","hit"]) == 0
    
    # Test case 6: Single step
    assert solution.ladderLength("cat", "bat", ["bat"]) == 2

Follow-up Questions

  1. Word Ladder II: Return all shortest transformation sequences
  2. Minimum Genetic Mutation: Similar problem with gene sequences
  3. Word Ladder with Costs: Each transformation has different costs
  4. Parallel Processing: How to parallelize the BFS search

Common Mistakes

  1. Forgetting Level Tracking: Not properly tracking the level in BFS
  2. Infinite Loops: Not marking words as visited
  3. Character Generation: Inefficient string manipulation
  4. Early Termination: Missing the check when endWord is found

Interview Tips

  1. Recognize BFS Pattern: Identify this as shortest path in unweighted graph
  2. Explain State Space: Clearly describe nodes (words) and edges (single character differences)
  3. Optimize Gradually: Start with basic BFS, then mention bidirectional optimization
  4. Handle Edge Cases: Always check if endWord exists in wordList
  5. Code Incrementally: Build word generation logic first, then integrate with BFS
  6. Discuss Trade-offs: Compare different approaches and their complexities
  1. Word Ladder II (LeetCode 126): Return all shortest paths
  2. Minimum Genetic Mutation (LeetCode 433): Similar transformation logic
  3. Open the Lock (LeetCode 752): State transformation with constraints
  4. Sliding Puzzle (LeetCode 773): 2D state space transformation

Optimization Techniques

  1. Bidirectional BFS: Search from both ends
  2. Pattern Matching: Use wildcard patterns for efficient neighbor finding
  3. Early Termination: Stop as soon as target is reached
  4. Set Operations: Use sets for O(1) lookup and membership testing