127. Word Ladder — DSA Atlas

127

HardGraph DFS and BFSBFS over an implicit word graphShortest transformation via BFS

Word Ladder

Given beginWord, endWord, and a word list, return the number of words in the shortest transformation sequence from beginWord to endWord, changing one letter at a time so that every intermediate word is in the list. Return 0 if no such sequence exists.

Open official problem prompt ↗

In plain English

Compute the length of the shortest single-letter-change path from the start word to the end word.

Picture it like this

Like navigating a maze of words where each door lets you swap exactly one letter; you want the fewest rooms to walk through to reach the target word.

Example

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Why: hit -> hot -> dot -> dog -> cog is 5 words, and no shorter valid chain exists.

Constraints

1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthAll words consist of lowercase English lettersbeginWord != endWordAll words in wordList are unique

Pattern lesson

See the pattern, then code

Shortest transformation via BFS

↗

Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. Treat each word as a node with edges to every word that differs by one letter; BFS from beginWord finds the fewest steps to endWord, and generating neighbors by trying all 26 letters at each position is cheaper than pairwise comparison.

New words, made simpleKnow these before the algorithm

Implicit graph: A graph whose edges are computed on demand rather than stored explicitly.
Unweighted shortest path: Fewest edges between two nodes, solved by BFS.
Neighbor generation: Building adjacent words by changing one character at a time.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Compare every pair of words

The N^2 pair comparison is too slow when N is up to 5000.

Build edges by checking all word pairs for a one-letter difference, then BFS.

Time O(N^2 * L)Space O(N^2)

Best choiceBFS with 26-letter neighbor generation

Neighbor cost depends on word length, not list size, so it scales.

Generate neighbors by substituting each of 26 letters at each position and checking the set.

Time O(N * L^2)Space O(N * L)

The rule we keep true

Invariant

The first time BFS dequeues a word, it has been reached by the shortest possible number of transformations from beginWord.

Why this is correct

Reasoning

BFS explores words in increasing distance order, so endWord is dequeued at its minimum distance; removing words from the set the moment they are enqueued guarantees each word is processed once and prevents cycles.

The algorithm in three movesSay these aloud before coding

1Put the word list in a set for O(1) membership and early exit if endWord is absent

queue=[(hit,1)]

2BFS from beginWord tracking the step count (words used so far)

(hot,2) -> (dot,3),(lot,3)

3For each position, try all 26 letters to form candidate neighbors in the set

(dog,4) -> (cog,5) return 5

4Remove each visited word from the set to avoid revisiting; return steps on reaching endWord

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

hot1

dot2

dog3

cog4

1 · ReadbeginWord=hit

2 · AskIs endWord in the set?

3 · Update statequeue=[(hit,1)]

4 · Resultcog present, begin BFS

Key takeaway

A shortest one-letter-change chain of five words from hit to cog.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-8Set and early exit
If the target is not in the list, no chain can exist.
2
Lines 9-12BFS with step count
Each queue entry carries how many words have been used; reaching endWord returns that count.
3
Lines 13-19Generate and prune neighbors
Every one-letter variant present in the set is enqueued and removed at once to mark it visited.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

endWord not in wordList returns 0
beginWord one letter from endWord returns 2
No possible chain returns 0
beginWord itself need not be in the word list

Common beginner mistakes

Not marking words visited, leading to revisits and timeouts
Comparing all pairs of words which is too slow at N=5000
Counting edges instead of words in the sequence, returning length off by one
Assuming beginWord is in the list; it may not be

Check your understanding

Why remove a word from the set as soon as it is enqueued rather than when it is dequeued?

PyPython 3 · solution.py

Optimal

1from collections import deque234class Solution:5    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:6        word_set = set(wordList)7        if endWord not in word_set:8            return 09        queue = deque([(beginWord, 1)])10        while queue:11            word, steps = queue.popleft()12            if word == endWord:13                return steps14            for i in range(len(word)):15                for ch in "abcdefghijklmnopqrstuvwxyz":16                    nxt = word[:i] + ch + word[i + 1:]17                    if nxt in word_set:18                        word_set.remove(nxt)19                        queue.append((nxt, steps + 1))20        return 0

Time complexityO(N * L^2) where N is list size and L is word lengthOptimized

Space complexityO(N * L)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMetaGoogleLinkedIn

Word Ladder

Word Ladder

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Graph DFS and BFS