Word Ladder | Leetcode 127 | Explained using BFS

Learn how to solve the Word Ladder problem by building a BFS over words, changing one letter at a time. This clear, line-by-line guide uses simple code comments and a dry run to show how we get the shortest transformation length.

What the Problem Asks

You have a beginWord, an endWord, and a list of allowed words (wordList).
You can change one letter at a time, but each intermediate word must be in the word list.
Return the fewest steps needed to go from beginWord to endWord. If it’s impossible, return 0.

Intuition & Approach

1. Breadth-First Search (BFS):
   • We treat each word as a node in a graph.
   • There’s an edge between two words if they differ by exactly one letter.
   • BFS from beginWord will find the shortest path to endWord.
2. Word Set for Fast Lookups:
   • Convert wordList to a set so we can check existence in O(1).
   • Remove words from the set when we visit them to avoid revisiting.
3. Level Tracking:
   • Each BFS queue entry holds (currentWord, stepsSoFar).
   • When we reach endWord, stepsSoFar is the answer.

Code Implementation (with Comments)

from collections import deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        # 1. Put all allowed words into a set for O(1) lookups.
        wordSet = set(wordList)
        # If endWord isn't in the list, we can never reach it.
        if endWord not in wordSet:
            return 0

        # 2. Initialize BFS queue with (beginWord, stepCount=1).
        queue = deque()
        queue.append((beginWord, 1))

        # 3. Standard BFS loop
        while queue:
            curr_word, level = queue.popleft()
            # If we've reached the end, return the number of steps.
            if curr_word == endWord:
                return level

            # 4. Try changing each letter in curr_word
            for i in range(len(curr_word)):
                # For each position, try all possible lowercase letters
                for ch in "abcdefghijklmnopqrstuvwxyz":
                    # Skip if the letter is the same
                    if ch == curr_word[i]:
                        continue
                    # Form a new word by replacing the i-th letter
                    new_word = curr_word[:i] + ch + curr_word[i+1:]
                    # If the new word is in our set, it's a valid step
                    if new_word in wordSet:
                        # Add it to the queue with stepCount + 1
                        queue.append((new_word, level + 1))
                        # Remove from set so we don't visit again
                        wordSet.remove(new_word)

        # If queue empties without finding endWord, there's no path
        return 0

Step-by-Step Explanation

1. Build wordSet:
   • Helps us quickly check if a transformed word is allowed.
2. BFS Queue:
   • Starts with the beginWord at step 1.
3. While Loop:
   • Pop the front word and its current step count.
   • If it matches endWord, we’re done.
4. Generate Neighbors:
   • For each position in curr_word, try replacing it with every letter a–z.
   • If the resulting new_word is in wordSet, it’s a valid move:
     • Enqueue (new_word, level+1).
     • Remove new_word from wordSet so we don’t revisit it.
5. No Path Found:
   • If BFS completes without hitting endWord, return 0.

Dry Run Example

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

• Step 1: queue = [(“hit”,1)], wordSet={“hot”,”dot”,”dog”,”lot”,”log”,”cog”}
• Step 2: pop (“hit”,1). Generate neighbors:
  • “hot” is valid → enqueue (“hot”,2), remove “hot”.
• Step 3: pop (“hot”,2). Neighbors:
  • “dot” → enqueue (“dot”,3), remove “dot”.
  • “lot” → enqueue (“lot”,3), remove “lot”.
• Step 4: pop (“dot”,3):
  • “dog” → enqueue (“dog”,4), remove “dog”.
• Step 5: pop (“lot”,3):
  • “log” → enqueue (“log”,4), remove “log”.
• Step 6: pop (“dog”,4):
  • “cog” → enqueue (“cog”,5), remove “cog”.
• Step 7: pop (“log”,4): also can reach “cog”, but it’s already removed.
• Step 8: pop (“cog”,5): matches endWord → return 5.

Result is 5.

Time & Space Complexity

• Time Complexity:
  • In the worst case, for each of N words and each word of length L, we try 26 replacements: O(N × L × 26).
• Space Complexity:
  • O(N) for the wordSet and O(N) for the BFS queue in the worst case.

Conclusion

By treating each word as a node and valid one-letter changes as edges, BFS finds the shortest transformation path in the fewest steps. The key tricks are:

• Using a set for fast lookups and removals.
• Enqueuing (word, steps) for level tracking.
• Removing words from wordSet as soon as they’re visited.

With this pattern, you can tackle many “word transformation” challenges in coding interviews. Happy coding!

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