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.

Example 1:

Input: beginWord = "led", endWord = "pen", wordList = ["bed","ben","pen"]
Output: 4
Explanation: the shortest transformation is "led" -> "bed" -> "ben" -> "pen".

Example 2:

Input: beginWord = "cut", endWord = "dim", wordList = ["cot","dot","dig"]
Output: 0
Explanation: the endWord "dim" is not in wordList, so no sequence exists.

Constraints:

• 1 <= beginWord.length <= 8
• endWord.length == beginWord.length
• 1 <= wordList.length <= 2000
• wordList[i].length == beginWord.length
• beginWord, endWord, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• All the words in wordList are unique.

Solution Breakdown

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 led -> pen example, BFS discovers bed at length 2, ben at 3, and matches pen at length 4.

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.