Word Ladder II | Leetcode 126 | Shortest Transformation Sequences with BFS

Learn how to find all shortest paths (Word Ladder II) from one word to another by changing one letter at a time. This guide uses a clear example, and in-place code comments to illustrate a level-by-level BFS approach.

Here’s the [Problem Link] to begin with.

What the Problem Asks

You have a beginWord, an endWord, and a list of words called wordList.
You want to transform beginWord into endWord by changing exactly one letter at a time.
Each new intermediate word must be in wordList.
Return all possible shortest sequences of words from beginWord to endWord.

Example 1

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

Shortest sequences:
  ["hit","hot","dot","dog","cog"]
  ["hit","hot","lot","log","cog"]

Example 2

beginWord = "a"
endWord   = "c"
wordList  = ["a","b","c"]

Shortest sequences:
  ["a","c"]

(“a” → “c” is valid because “c” is in the list, and we changed one letter.)

Also read about the Python Program to Solve Word Ladder – 1.

Intuition & Approach

1. We want all shortest sequences, not just one.
2. BFS layer by layer naturally finds the shortest distance.
3. At each step, we keep whole sequences in the queue (not just words).
4. We also remove words from the set once they appear at the current level, so later levels don’t reuse them and produce longer paths.

In very simple terms:

• Start with a queue of lists, each list is a transformation path so far.
• In each iteration, we pop a path, look at its last word, generate all possible “one-letter” changes.
• If a changed word is in wordSet, we make a new path by appending that word and push it into the queue.
• As soon as we see a path ending in endWord, we record it—because BFS guarantees this is the shortest length.
• We keep collecting all such paths until we finish processing the current BFS layer.
• Finally, we return all collected shortest paths.

Code

from collections import deque

class Solution:
    def findLadders(
        self, beginWord: str, endWord: str, wordList: List[str]
    ) -> List[List[str]]:
        # 1. Put all words into a set for fast lookups
        wordSet = set(wordList)
        # If the endWord is not in our list, we can’t transform to it
        if endWord not in wordSet:
            return []

        result = []              # To store all shortest sequences
        queue = deque()          # BFS queue of paths (lists of words)
        queue.append([beginWord])  # Start with the path ["beginWord"]

        while len(queue) != 0:
            level_size = len(queue)
            chosen_words = set()  # Words we will remove after this layer

            # Process everything in the current layer
            for _ in range(level_size):
                sequence = queue.popleft()   # A path so far
                last_word = sequence[-1]      # The most recent word

                # If we already reached endWord, record this path
                if last_word == endWord:
                    result.append(sequence)
                    # Don’t continue expanding this path; it’s complete
                    continue

                # Try changing each letter of last_word
                for i in range(len(last_word)):
                    for ch in "abcdefghijklmnopqrstuvwxyz":
                        # Skip if the letter is the same
                        if ch == last_word[i]:
                            continue
                        # Form a new word by replacing the i-th letter
                        new_word = last_word[:i] + ch + last_word[i + 1:]
                        # If this new word is in our set, it’s valid
                        if new_word in wordSet:
                            # Make a new path by appending new_word
                            new_seq = sequence + [new_word]
                            queue.append(new_seq)
                            # Mark new_word for removal after this layer
                            chosen_words.add(new_word)

            # Remove all words that were used in this layer
            for w in chosen_words:
                wordSet.remove(w)

        return result

How the Code Works, Step by Step

1. wordSet = set(wordList)
   • We need to quickly check if a candidate word is allowed. A Python set does that in O(1).
2. If endWord not in wordSet, return []
   • If you can’t ever reach the target word, answer is empty.
3. Initialize
   • result = [] will hold all shortest paths we find.
   • queue holds paths. Start with just [beginWord].
4. While queue is not empty
   • level_size = len(queue) captures how many paths are in this BFS level.
   • chosen_words = set() to track which new words we used in this level.
5. Process each path in the current BFS level
   • sequence = queue.popleft(): get the next path.
   • last_word = sequence[-1]: look at the last word in that path.
   • If last_word == endWord, we found a complete shortest path. Append it to result and do not extend it further (because BFS guarantees this is minimal length).
   • Otherwise, generate neighbors by changing one letter at a time:
     • For each position i in last_word, try every letter a–z.
     • Skip if the letter is unchanged.
     • Form new_word.
     • If new_word is in wordSet, it’s a valid next step:
       • new_seq = sequence + [new_word] builds a new path list.
       • Enqueue new_seq.
       • Add new_word to chosen_words so that at the end of this layer we remove it from wordSet.
6. After finishing this entire BFS layer, remove all chosen_words from wordSet.
   • This prevents paths in deeper layers (longer paths) from reusing the same words and ensures we only collect shortest sequences.
7. Return result
   • All recorded paths in result have length equal to the shortest transformation count.

Dry Run with Example

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

1. Initialize:
   • wordSet = {"hot","dot","dog","lot","log","cog"}
   • queue = [["hit"]].
2. Layer 1 (size=1):
   • Sequence: ["hit"], last_word=”hit”
   • Generate neighbors of “hit”:
     • Change “h”→“a”..“z” except “h”; only valid is “hot”.
   • New path ["hit","hot"], queue it.
   • chosen_words = {"hot"}.
   • End layer, remove “hot” from wordSet.
3. Layer 2 (size=1):
   • Sequence: ["hit","hot"], last_word=”hot”
   • Generate neighbors for “hot”:
     • “dot” and “lot” are valid (in wordSet).
   • Enqueue ["hit","hot","dot"] and ["hit","hot","lot"].
   • chosen_words = {"dot","lot"}.
   • Remove them from wordSet.
4. Layer 3 (size=2):
   • Sequence ["hit","hot","dot"], last_word=”dot”
     • Valid neighbor: “dog” → enqueue ["hit","hot","dot","dog"].
   • Sequence ["hit","hot","lot"], last_word=”lot”
     • Valid neighbor: “log” → enqueue ["hit","hot","lot","log"].
   • chosen_words = {"dog","log"}.
   • Remove “dog” and “log” from wordSet.
5. Layer 4 (size=2):
   • Sequence ["hit","hot","dot","dog"], last_word=”dog”
     • Valid neighbor: “cog” → enqueue ["hit","hot","dot","dog","cog"].
   • Sequence ["hit","hot","lot","log"], last_word=”log”
     • Valid neighbor: “cog” → enqueue ["hit","hot","lot","log","cog"].
   • chosen_words = {"cog"}.
   • Remove “cog” from wordSet.
6. Layer 5 (size=2):
   • Sequence ["hit","hot","dot","dog","cog"], last_word=”cog” → matches endWord, record it in result.
   • Sequence ["hit","hot","lot","log","cog"], last_word=”cog” → record it in result.
7. Return
   • result = [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ].

Time & Space Complexity

• Time Complexity:
  • BFS can enqueue up to O(N × L) paths in the worst case, where N = number of words and L = word length.
  • Each path expansion tries L positions × 26 letters → O(26 × L) checks per path.
  • Overall roughly O(N × L × 26), which is acceptable for moderate input sizes.
• Space Complexity:
  • Storing all partial paths and a word set → O(N × L) in total.

Conclusion

By using a level-by-level BFS where each queue entry is a full transformation path, we automatically find the shortest sequences. Removing each new word from the set at the end of its layer ensures we never revisit longer paths. This simple method collects all shortest paths in a clean, easy-to-follow way. Happy coding!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.