Visualize

Pattern visualizer

Word Ladder

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. Animated on: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] — length of the shortest transformation sequence, or 0..

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

time O(N * 26 * L^2)space O(N * L)step 1 / 10

Every one-letter change is an edge

line 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.

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

Where to practice Graph

Practice Graph problemsAll Graph problemsBack to roadmap