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

What Is LeetCode 126: Word Ladder II?

In LeetCode 126: Word Ladder II, you’re given a start word beginWord, an end word endWord, and a list of words wordList. Your task is to find all shortest transformation sequences from beginWord to endWord, where each step changes exactly one letter, and every intermediate word must be in wordList. For example, with beginWord = "hit", endWord = "cog", and wordList = ["hot", "dot", "dog", "lot", "log", "cog"], the output is [["hit", "hot", "dot", "dog", "cog"], ["hit", "hot", "lot", "log", "cog"]].

Problem Statement

• Input: Strings beginWord and endWord, and a list wordList.
• Output: A list of lists—all shortest transformation sequences.
• Rules:
• Change one letter per step.
• Intermediate words must be in wordList.
• Return all shortest paths (same length).
• Return empty list if no path 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: [["hit", "hot", "dot", "dog", "cog"], ["hit", "hot", "lot", "log", "cog"]]
• Why: Two shortest paths of length 5.
• Input: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log"]
• Output: []
• Why: No path to "cog" (missing in wordList).
• Input: beginWord = "red", endWord = "tax", wordList = ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"]
• Output: [["red", "ted", "tax"], ["red", "tex", "tax"]]
• Why: Two shortest paths of length 3.

Understanding the Problem: Climbing the Word Ladder

To solve LeetCode 126: Word Ladder II in Python, we need to find all shortest paths in a word transformation graph, where nodes are words and edges connect words differing by one letter. A naive approach—trying every possible sequence—would be exponential, impractical for 5000 words. Instead, we’ll use graph traversal:

• Best Solution (Bidirectional BFS): O(26 * n * w) time, O(n * w) space—fast and path-efficient.
• Alternative Solution (Single BFS with Backtracking): O(26 * n * w) time, O(n * w) space—simpler but less optimized.

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

Best Solution: Bidirectional BFS with Path Reconstruction

Why This Is the Best Solution

The bidirectional BFS approach is the top pick because it’s highly efficient—reducing the search space by exploring from both ends—and balances time and space well. It uses two queues to find the shortest path length, then reconstructs all paths of that length, leveraging the overlap point. It’s like sending two climbers from the top and bottom of a ladder, meeting in the middle to map all shortest routes—smart and scalable!

How It Works

Here’s the strategy:

• Step 1: Setup:
• Convert wordList to a set, add beginWord if not present.
• Check if endWord is in set; if not, return [].
• Step 2: Bidirectional BFS:
• Use two sets: start_set (beginWord), end_set (endWord).
• Track visited words and neighbors per word per direction.
• Expand the smaller set each step, swapping if needed.
• Stop when sets overlap (shortest path found).
• Step 3: Path Reconstruction:
• Use neighbor dictionaries to backtrack all paths from overlap.
• Step 4: Return:
• List all shortest sequences.

Step-by-Step Example

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

• Setup: word_set = {"hit", "hot", "dot", "dog", "lot", "log", "cog"}.
• BFS:
• start_set = {"hit"}, end_set = {"cog"}.
• Level 1 (start):
• "hit" → "hot" (h*t → hot).
• start_set = {"hot"}, start_neighbors["hit"] = {"hot"}.
• Level 1 (end):
• "cog" → "log", "dog".
• end_set = {"log", "dog"}, end_neighbors["cog"] = {"log", "dog"}.
• Level 2 (start):
• "hot" → "dot", "lot".
• start_set = {"dot", "lot"}, start_neighbors["hot"] = {"dot", "lot"}.
• Level 2 (end):
• "log" → "lot", "dog" → "dot".
• end_set = {"lot", "dot"}, overlap with start_set!
• Path Reconstruction:
• Overlap: "dot", "lot".
• From "hit":
• "hit" → "hot" → "dot".
• "hit" → "hot" → "lot".
• From "cog":
• "cog" → "dog" → "dot".
• "cog" → "log" → "lot".
• Combine:
• "hit" → "hot" → "dot" → "dog" → "cog".
• "hit" → "hot" → "lot" → "log" → "cog".
• Result: [["hit", "hot", "dot", "dog", "cog"], ["hit", "hot", "lot", "log", "cog"]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

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

        # Step 2: Bidirectional BFS
        start_set = {beginWord}
        end_set = {endWord}
        start_neighbors = defaultdict(set)
        end_neighbors = defaultdict(set)
        found = False

        while start_set and end_set and not found:
            if len(start_set) > len(end_set):
                start_set, end_set = end_set, start_set
                start_neighbors, end_neighbors = end_neighbors, start_neighbors

            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:
                            found = True
                            start_neighbors[word].add(new_word)
                            end_neighbors[new_word].add(word)
                        elif new_word in word_set and new_word not in start_neighbors:
                            next_set.add(new_word)
                            start_neighbors[word].add(new_word)
            start_set = next_set
            word_set -= next_set

        # Step 3: Path reconstruction
        def build_paths(start, end, forward_neighbors, backward_neighbors, path, result):
            if start == end:
                result.append(path[:])
                return
            for next_word in forward_neighbors[start]:
                if next_word in backward_neighbors:
                    path.append(next_word)
                    build_paths(next_word, end, forward_neighbors, backward_neighbors, path, result)
                    path.pop()

        result = []
        build_paths(beginWord, endWord, start_neighbors, end_neighbors, [beginWord], result)
        return result

• Line 4-8: Setup word set, check endWord.
• Line 11-34: Bidirectional BFS:
• Line 17-19: Swap if start_set grows larger.
• Line 22-30: Generate neighbors, check overlap.
• Line 32-33: Update sets for next level.
• Line 37-45: Recursive path builder.
• Time Complexity: O(26 * n * w)—n words, w length, 26 letters.
• Space Complexity: O(n * w)—neighbor storage.

This is a ladder-climbing maestro!

Alternative Solution: Single-Direction BFS with Backtracking

Why an Alternative Approach?

The single-direction BFS with backtracking is simpler to grasp—O(26 * n * w) time, O(n * w) space—using one queue and reconstructing paths afterward. It’s like climbing from the start, noting all steps, then tracing back the shortest routes—straightforward but less optimized.

How It Works

• Step 1: BFS to find shortest length and neighbors.
• Step 2: Backtrack from end to start using neighbors.

Step-by-Step Example

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

• BFS:
• Level 0: "hit".
• Level 1: "hot".
• Level 2: "dot", "lot".
• Level 3: "dog", "log".
• Level 4: "cog" (found).
• Neighbors: "hit" → "hot", "hot" → "dot", "lot", etc.
• Backtrack:
• "cog" → "dog" → "dot" → "hot" → "hit".
• "cog" → "log" → "lot" → "hot" → "hit".
• Result: Same as above.

Code for Single BFS Approach

Copy codeclass Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        word_set = set(wordList)
        if endWord not in word_set:
            return []

        # BFS
        queue = deque([(beginWord, 1)])
        neighbors = defaultdict(list)
        levels = {beginWord: 1}
        while queue:
            word, level = queue.popleft()
            if word == endWord:
                break
            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 levels or levels[new_word] == level + 1):
                        queue.append((new_word, level + 1))
                        neighbors[word].append(new_word)
                        levels[new_word] = level + 1

        # Backtrack
        def build_paths(word, path, result):
            if word == beginWord:
                result.append(path[::-1])
                return
            for prev_word in neighbors:
                if word in neighbors[prev_word]:
                    path.append(prev_word)
                    build_paths(prev_word, path, result)
                    path.pop()

        result = []
        build_paths(endWord, [endWord], result)
        return result

• Line 11-22: BFS to map neighbors and levels.
• Line 25-34: Backtrack to build paths.
• Time Complexity: O(26 * n * w).
• Space Complexity: O(n * w).

It’s a step-by-step pathfinder!

Comparing the Two Solutions

• Bidirectional BFS (Best):
• Pros: Faster due to smaller search space, O(26 * n * w) time, O(n * w) space.
• Cons: More complex setup.
• Single BFS (Alternative):
• Pros: Simpler logic, same time complexity.
• Cons: Larger search space, less efficient.

Bidirectional wins for speed.

Additional Examples and Edge Cases

• "a", "c", ["a", "b", "c"]: [["a", "c"]].
• "hit", "cog", ["hot"]: [].

Both handle these well.

Complexity Breakdown

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

Bidirectional’s efficiency shines.

Key Takeaways

• Bidirectional: Meet in the middle!
• Single BFS: Climb and trace!
• Paths: Shortest is key.
• Python Tip: Sets speed up—see [Python Basics](/python/basics).

Final Thoughts: Climb the Ladder

LeetCode 126: Word Ladder II in Python is a word-transforming quest. Bidirectional BFS scales with flair, while single BFS offers clarity. Want more ladder fun? Try LeetCode 127: Word Ladder or LeetCode 433: Minimum Genetic Mutation. Ready to transform? Head to Solve LeetCode 126 on LeetCode and find those paths today!