Word Ladder

Problem

Code deployment pipelines sometimes require staged rollouts where each intermediate configuration must be a valid known state. The word ladder problem models this: given a start configuration and target, find the shortest sequence of one-step changes where each intermediate state is valid. Each step changes exactly one character and the result must appear in the allowed-states dictionary.

beginWord = "hit", endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
→ 5  ("hit" → "hot" → "dot" → "dog" → "cog")
 
beginWord = "hit", endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
→ 0  (endWord not reachable)

Solution

Approach: BFS over an implicit graph where words differing by one letter are neighbors.

We never build the graph explicitly - instead we generate a word's neighbors on the fly. For each word popped from the queue, we walk every character position i and try all 26 letters, forming a candidate with word[:i] + chr(ord('a') + j) + word[i+1:]. A candidate is a real edge only if it appears in word_set (the dictionary, stored as a set for O(1) membership). BFS explores all words at sequence length k before any at k+1, so the first time we generate end_word we have reached it in the fewest transformations - that is why we can return length + 1 the instant a candidate matches the target.

We track length in each queue tuple, starting at (begin_word, 1) since the sequence length counts both endpoints. Visited words are recorded in a visited set so a word is enqueued only once, preventing cycles and redundant expansion. On the classic hit -> cog example, BFS discovers hot at length 2, dot/lot at 3, dog/log at 4, and matches cog at length 5.

Edge cases: if end_word is not in word_set, no sequence can end there, so we return 0 up front. begin_word need not be in the dictionary - it is enqueued directly. If the queue drains without producing end_word, we return 0.

Complexity: O(n * L^2) time where n is the dictionary size and L the word length - each word spawns L * 26 candidates, each an O(L) string build. O(n * L) space for the set, queue, and visited words.