DSA Tracker

Visualize

Word Ladder

BFS over words: one letter per step, shortest sequence wins

time O(N * 26 * L^2)space O(N * L)

Treat every word as a vertex and every one-letter change as an edge, and the problem becomes the shortest path in an unweighted graph — which is breadth-first search. Nobody builds that graph up front: from each word, swap every position for every letter a to z and keep the candidates that are still in the word set. Erasing a word from the set the moment it is discovered is what keeps the search linear, because the first route to reach a word is already the shortest, so no later route needs it. The badge on each node is the ladder length that reached it.

Details

Animated on: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] — length of the shortest transformation sequence, or 0.

Problem:Word LadderHard

BFS over words: one letter per step, shortest sequence wins

step 1 / 10

Every one-letter change is an edge

"hit" must become "cog" one letter at a time, and every intermediate word has to be in the list. Each line here joins two words that differ in exactly one letter — so the question is the shortest path in an unweighted graph, and that is exactly what breadth-first search finds.

Pseudocode
1FUNCTION ladderLength(beginWord, endWord, wordList):
2  dict <- SET OF wordList
3  IF endWord NOT IN dict RETURN 0
4  queue <- [(beginWord, 1)]
5  WHILE queue NOT EMPTY
6    (word, steps) <- REMOVE FIRST FROM queue
7    IF word = endWord RETURN steps
8    FOR i FROM 0 TO LENGTH(word) - 1
9      FOR EACH c IN 'a' TO 'z'
10        next <- word WITH word[i] REPLACED BY c
11        IF next IN dict
12          REMOVE next FROM dict
13          APPEND (next, steps + 1) TO queue
14  RETURN 0

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. "hit" must become "cog" one letter at a time, and every intermediate word has to be in the list. Each line here joins two words that differ in exactly one letter — so the question is the shortest path in an unweighted graph, and that is exactly what breadth-first search finds.
  2. First check "cog" is in the list of 6 words — it is, so a ladder is possible. Without this check the search would run to exhaustion for nothing.
  3. Queue "hit" with ladder length 1 — the sequence counts words, not changes, so the start word alone is already a ladder of length 1.
  4. Take "hit" (badge 1) and try all 26 letters in each of its 3 positions — 78 candidates, but only "hot" is still in the set. It gets badge 2 and is erased from the set, so no later, longer route can ever re-add it. Queue: "hot".
  5. Take "hot" (badge 2) and try all 26 letters in each of its 3 positions — 78 candidates, but only "dot" and "lot" are still in the set. They get badge 3 and are erased from the set, so no later, longer route can ever re-add them. Queue: "dot", "lot".
  6. Take "dot" (badge 3) and try all 26 letters in each of its 3 positions — 78 candidates, but only "dog" is still in the set. It gets badge 4 and is erased from the set, so no later, longer route can ever re-add it. Queue: "lot", "dog".
  7. Take "lot" (badge 3) and try all 26 letters in each of its 3 positions — 78 candidates, but only "log" is still in the set. It gets badge 4 and is erased from the set, so no later, longer route can ever re-add it. Queue: "dog", "log".
  8. Take "dog" (badge 4) and try all 26 letters in each of its 3 positions — 78 candidates, but only "cog" is still in the set. It gets badge 5 and is erased from the set, so no later, longer route can ever re-add it. Queue: "log", "cog".
  9. Take "log" (badge 4) and try every one-letter change — nothing left in the set matches, because every neighbour was already claimed by an earlier, shorter route. Queue: "cog".
  10. The word leaving the queue is "cog" itself, with badge 5. BFS grows one level at a time, so the first time the end word comes off the queue its level is the shortest possible: hit -> hot -> dot -> dog -> cog. RETURN 5.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Word Ladder in the editorAll Graph problemsBack to roadmap