Problem Statement

Word Ladder

You start at one word, beginWord, and you want to reach another word, endWord. The only move you are allowed is to change exactly one letter at a time, and every word you pass through along the way must be a real word from the given list, wordList. So "hot" can become "dot" (one letter changed), but "hit" cannot jump straight to "cog". Your job is to find the shortest chain of words from start to finish and return how many words are in that chain. If there is no way to get there, return 0.

hardGraphsBFSGraphsTime: O(M^2 * N) · Space: O(M^2 * N)

Signals to notice

shortest transformation sequencechange one letter at a timeeach intermediate must be valid

Brute force first

DFS trying all possible one-letter changes — exponential. Explores deep paths when the shortest one might be shallow. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

BFS from the start word: each level represents one transformation step. Generate all valid one-letter changes, check against the word list. The first time you reach the end word is the shortest path. where M = word length, N = word list size. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log","cog"]`

init: endWord "cog" in set OK; queue=[("hit",1)], visited={hit}
pop ("hit",1): mutate each pos -> "hot" in set, new -> queue=[("hot",2)], visited+={hot}
pop ("hot",2): "dot" and "lot" valid & unseen -> queue=[("dot",3),("lot",3)], visited+={dot,lot}
pop ("dot",3): "dog" valid & unseen -> queue=[("lot",3),("dog",4)], visited+={dog}
pop ("lot",3): "log" valid & unseen -> queue=[("dog",4),("log",4)], visited+={log}
pop ("dog",4): mutating pos 0 -> "cog" == endWord -> return steps+1 = 5

What must stay true

BFS guarantees the shortest path in an unweighted graph. Each word is a node; edges connect words differing by one letter. The first time BFS reaches the target is the minimum number of transformations. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

queue = [(beginWord, 1)]; visited = {beginWord}
while queue:
    word, steps = queue.popleft()
    for each position i, for each letter c:
        new = word with position i replaced by c
        if new == endWord: return steps + 1
        if new in wordSet and not visited: visit it, queue.append((new, steps+1))

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Using DFS instead of BFS — DFS finds A path but not necessarily the shortest. Also, generating neighbors by trying all 26 letters at each position is often faster than comparing against every word in the list. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Graphs Pattern