Word Ladder - BFS Explained Step by Step

Why it works

BFS explores the graph in rings of increasing distance, so the first ring that contains the end word is by definition the shortest path. Visiting each word once bounds the work at O(n·m²) for n words of length m - a DFS would happily wander past shorter paths first.

The problem

Given two words beginWord and endWord and a word list, return the length of the shortest transformation sequence from beginWord to endWord where each step changes exactly one letter and all intermediate words are in the word list.

Hints

• BFS from beginWord, each level = one transformation.
• For each word position, try all 26 letters to generate neighbors.
• Store neighbors in a set for O(1) lookup.
• Mark words as visited when added to the queue, not when dequeued.

Test cases

Reference starter code

from collections import deque

def ladder_length(beginWord, endWord, wordList):
    word_set = set(wordList)
    if endWord not in word_set:
        return 0
    queue = deque([(beginWord, 1)])
    visited = {beginWord}
    while queue:
        word, length = queue.popleft()
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + c + word[i+1:]
                if new_word == endWord:
                    return length + 1
                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, length + 1))
    return 0

print(ladder_length("hit", "cog", ["hot","dot","dog","lot","log","cog"]))  # 5
print(ladder_length("hit", "cog", ["hot","dot","dog","lot","log"]))         # 0

Try it yourself

Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.