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

What Is LeetCode 127: Word Ladder?

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

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

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

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

• 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

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

Both handle these well.

Complexity Breakdown

• 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

• 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

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!