HardGraphs · Breadth-first search

Word Ladder

Turn beginWord into endWord by changing one letter at a time, where every intermediate word (and endWord) must be in wordList. Return the number of words in the shortest such sequence, counting beginWord, or 0 if none exists.

cat → sag, [bat,bag,sag,dag,dot] → 4cat → sag, [bat,bag,sat,dag,dot] → 0

Try:
CALL
1 / 1

Code

The highlighted line runs next. The pill shows the live values in the running call.

Variables

The data structures the code is building

Word graph

Edges join words one letter apart; columns = distance from beginWord

current wordbadge = ladder length so faredge used to discover a wordbeing followed

Time and space complexity

n = words in wordList, m = word length. The highlighted row is the solution being traced.

Keyboard: ← → step, Space play or pause. Words up to 5 letters, at most 12 in wordList, separated by commas. Words that beginWord can never reach are drawn in the last column.