LeetCode 127: Word Ladder Solution in Python – A Step-by-Step Guide

Imagine you’re given a starting word like "hit", an ending word like "cog", and a list of words like ["hot", "dot", "dog", "lot", "log", "cog"]. Your mission? Find the shortest number of steps to transform "hit" into "cog", changing one letter at a time, where each step must be a valid word from the list. This is LeetCode 127: Word Ladder, a medium-level problem that’s a captivating blend of graph traversal and wordplay. Using Python, we’ll explore two effective solutions: the Best Solution, a bidirectional BFS that’s fast and efficient, and an Alternative Solution, a single-direction BFS that’s simpler to grasp. With detailed examples, code breakdowns, and a friendly tone, this guide will help you climb that word ladder—whether you’re prepping for an interview or just love a good challenge. Let’s start transforming and count those steps!

What Is LeetCode 127: Word Ladder?

Section link icon

In LeetCode 127: Word Ladder, you’re given a start word beginWord, an end word endWord, and a list of words wordList. Your task is to find the length of the shortest transformation sequence from beginWord to endWord, where each step changes exactly one letter, and every intermediate word must be in wordList. If no sequence exists, return 0. For example, with beginWord = "hit", endWord = "cog", and wordList = ["hot", "dot", "dog", "lot", "log", "cog"], the shortest sequence is 5 (e.g., "hit" → "hot" → "dot" → "dog" → "cog").

Problem Statement

  • Input: Strings beginWord and endWord, and a list wordList.
  • Output: An integer—the length of the shortest transformation sequence (including start and end words).
  • Rules:
    • Change one letter per step.
    • Intermediate words must be in wordList.
    • Return 0 if no sequence exists.

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.
  • beginWord != endWord, all words in wordList are unique.

Examples

  • Input: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
    • Output: 5
    • Why: "hit" → "hot" → "dot" → "dog" → "cog" (5 steps).
  • Input: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log"]
    • Output: 0
    • Why: No path to "cog" (missing from wordList).
  • Input: beginWord = "red", endWord = "tax", wordList = ["ted", "tex", "red", "tax"]
    • Output: 3
    • Why: "red" → "ted" → "tax" (3 steps).

Understanding the Problem: Measuring the Ladder

Section link icon

To solve LeetCode 127: Word Ladder in Python, we need to find the shortest path length in a word transformation graph, where nodes are words and edges connect words differing by one letter. A brute force approach—generating all sequences—would be exponential, impractical for 5000 words. Instead, we’ll treat it as a shortest-path problem using BFS:

  • Best Solution (Bidirectional BFS): O(26 * n * w) time, O(n) space—fast by searching from both ends.
  • Alternative Solution (Single BFS): O(26 * n * w) time, O(n) space—simpler but searches more.

Let’s dive into the Best Solution—bidirectional BFS—and break it down step-by-step.

Best Solution: Bidirectional BFS

Section link icon

Why This Is the Best Solution

The bidirectional BFS is the top choice because it’s significantly faster than single-direction BFS by reducing the search space—O(26 * n * w) time, O(n) space—where n is the word list size and w is word length. It explores from both the start and end words simultaneously, meeting in the middle to find the shortest path. It’s like sending two climbers from opposite ends of a ladder, cutting the distance they need to cover—efficient and clever!

How It Works

Here’s the strategy:

  • Step 1: Setup:
    • Convert wordList to a set, check if endWord is present (return 0 if not).
  • Step 2: Bidirectional BFS:
    • Use two sets: start_set (beginWord), end_set (endWord).
    • Track visited words and level (distance).
    • Expand the smaller set each step, swapping if needed.
    • Stop when sets overlap (shortest path found).
  • Step 3: Return Length:
    • Sum levels from both directions plus 1 (for overlap).

Step-by-Step Example

Example: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]

  • Setup: word_set = {"hot", "dot", "dog", "lot", "log", "cog", "hit"}.
  • BFS:
    • start_set = {"hit"}, start_visited = {"hit": 1}.
    • end_set = {"cog"}, end_visited = {"cog": 1}.
    • Level 1 (start):
      • "hit" → "hot".
      • start_set = {"hot"}, start_visited = {"hit": 1, "hot": 2}.
    • Level 1 (end):
      • "cog" → "log", "dog".
      • end_set = {"log", "dog"}, end_visited = {"cog": 1, "log": 2, "dog": 2}.
    • Level 2 (start):
      • "hot" → "dot", "lot".
      • start_set = {"dot", "lot"}, start_visited = {"hit": 1, "hot": 2, "dot": 3, "lot": 3}.
    • Level 2 (end):
      • "log" → "lot", "dog" → "dot".
      • end_set = {"lot", "dot"}, overlap with start_set!
    • Overlap: "dot" and "lot".
      • "dot": start level 3 + end level 2 - 1 = 4.
      • "lot": start level 3 + end level 2 - 1 = 4.
  • Result: 5 (verified path length).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        # Step 1: Setup
        word_set = set(wordList)
        if endWord not in word_set:
            return 0
        word_set.add(beginWord)

        # Step 2: Bidirectional BFS
        start_set = {beginWord}
        end_set = {endWord}
        start_visited = {beginWord: 1}
        end_visited = {endWord: 1}

        while start_set and end_set:
            # Expand smaller set
            if len(start_set) > len(end_set):
                start_set, end_set = end_set, start_set
                start_visited, end_visited = end_visited, start_visited

            next_set = set()
            for word in start_set:
                for i in range(len(word)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        new_word = word[:i] + c + word[i+1:]
                        if new_word in end_set:
                            return start_visited[word] + end_visited[new_word] - 1
                        if new_word in word_set and new_word not in start_visited:
                            next_set.add(new_word)
                            start_visited[new_word] = start_visited[word] + 1
            start_set = next_set
            word_set -= next_set

        return 0
  • Line 4-7: Setup word set, check endWord.
  • Line 10-13: Initialize sets and visited dictionaries.
  • Line 15-29: Bidirectional BFS:
    • Line 17-19: Swap if start_set grows larger.
    • Line 22-27: Generate neighbors, check overlap or add to next level.
    • Line 28-29: Update sets.
  • Line 31: Return 0 if no path found.
  • Time Complexity: O(26 * n * w)—n words, w length, 26 letters.
  • Space Complexity: O(n)—visited sets.

This is a ladder-measuring marvel!

Alternative Solution: Single-Direction BFS

Section link icon

Why an Alternative Approach?

The single-direction BFS is simpler to understand—O(26 * n * w) time, O(n) space—using a queue to explore from the start word until reaching the end. It’s like climbing the ladder step-by-step from the bottom, counting as you go—straightforward but searches more nodes than bidirectional.

How It Works

  • Step 1: Setup word set and queue.
  • Step 2: BFS with level tracking.
  • Step 3: Return level when endWord found, or 0 if not.

Step-by-Step Example

Example: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]

  • Setup: word_set = {"hot", "dot", "dog", "lot", "log", "cog"}.
  • BFS:
    • Level 1: "hit".
    • Level 2: "hot".
    • Level 3: "dot", "lot".
    • Level 4: "dog", "log".
    • Level 5: "cog" (found).
  • Result: 5.

Code for Single BFS Approach

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        word_set = set(wordList)
        if endWord not in word_set:
            return 0

        queue = deque([(beginWord, 1)])
        visited = {beginWord}

        while queue:
            word, level = queue.popleft()
            if word == endWord:
                return level
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    new_word = word[:i] + c + word[i+1:]
                    if new_word in word_set and new_word not in visited:
                        queue.append((new_word, level + 1))
                        visited.add(new_word)

        return 0
  • Line 4-6: Setup and check.
  • Line 8-9: Initialize queue and visited set.
  • Line 11-19: BFS loop:
    • Line 13-14: Return level if end found.
    • Line 16-19: Add unvisited neighbors.
  • Time Complexity: O(26 * n * w).
  • Space Complexity: O(n).

It’s a steady ladder climber!

Comparing the Two Solutions

Section link icon
  • Bidirectional BFS (Best):
    • Pros: Faster due to smaller search space, O(26 * n * w) time, O(n) space.
    • Cons: More complex setup.
  • Single BFS (Alternative):
    • Pros: Simpler logic, same complexity.
    • Cons: Explores more nodes.

Bidirectional wins for efficiency.

Additional Examples and Edge Cases

Section link icon
  • "a", "c", ["a", "b", "c"]: 2.
  • "hit", "cog", ["hot"]: 0.
  • "dog", "cat", ["dat", "cat"]: 2.

Both handle these well.

Complexity Breakdown

Section link icon
  • Bidirectional: Time O(26 * n * w), Space O(n).
  • Single BFS: Time O(26 * n * w), Space O(n).

Bidirectional’s speed shines.

Key Takeaways

Section link icon
  • Bidirectional: Meet in the middle!
  • Single BFS: Climb steadily!
  • Shortest Path: BFS is key.
  • Python Tip: Sets optimize—see [Python Basics](/python/basics).

Final Thoughts: Step Up the Ladder

Section link icon

LeetCode 127: Word Ladder in Python is a word-transforming journey. Bidirectional BFS scales with speed, while single BFS offers simplicity. Want more ladder challenges? Try LeetCode 126: Word Ladder II or LeetCode 433: Minimum Genetic Mutation. Ready to climb? Head to Solve LeetCode 127 on LeetCode and measure that ladder today!