DSA Tracker

Visualize

Word Ladder II

BFS by whole levels builds a parent DAG; DFS backtracking reads off every shortest path

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

Finding ONE shortest ladder is plain BFS. Finding ALL of them needs one more idea: a word must not be removed from the dictionary until its whole BFS level has finished expanding, so that two different words at the same level can both claim it as a parent — that is exactly what happens to "cog" below, reached from both "dog" and "log" on the same level. BFS still only tracks one number per word, its distance, but now also a list of parents instead of a single one. Once the target is found, walking those parent links backward with DFS reconstructs every sequence that is exactly that short.

Details

Animated on: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] — return every shortest transformation sequence from beginWord to endWord.

Problem:Word Ladder IIHard

BFS by whole levels builds a parent DAG; DFS backtracking reads off every shortest path

step 1 / 9

Every one-letter-apart pair is an edge

Treat "hit" and every word in the list as a vertex, and join two words with an edge whenever they differ in exactly one letter. The shortest transformation sequence is now just the shortest path in this graph — and because it is unweighted, that means BFS by level, expanding every word in a level before moving to the next.

Pseudocode
1FUNCTION findLadders(beginWord, endWord, wordList):
2  dict <- SET OF wordList
3  IF endWord NOT IN dict RETURN []
4  level <- {beginWord}
5  parents <- EMPTY MAP
6  WHILE level NOT EMPTY AND endWord NOT FOUND
7    REMOVE EVERY WORD IN level FROM dict
8    next <- EMPTY SET
9    FOR EACH word IN level
10      FOR EACH candidate ONE LETTER FROM word
11        IF candidate IN dict
12          ADD candidate TO next
13          APPEND word TO parents[candidate]
14    level <- next
15  RETURN ALL PATHS FROM beginWord TO endWord VIA parents

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. Treat "hit" and every word in the list as a vertex, and join two words with an edge whenever they differ in exactly one letter. The shortest transformation sequence is now just the shortest path in this graph — and because it is unweighted, that means BFS by level, expanding every word in a level before moving to the next.
  2. Level 0 is just "hit" itself, at distance 0.
  3. Mutating every letter of hit lands on hot still sitting in the dictionary. Distance 1 for all of them.
  4. Mutating every letter of hot lands on dot and lot still sitting in the dictionary. Distance 2 for all of them.
  5. Mutating every letter of dot and lot lands on dog and log still sitting in the dictionary. Distance 3 for all of them.
  6. Mutating every letter of dog and log lands on cog still sitting in the dictionary — and cog is reached from more than one word at this level, so it gets more than one parent. Distance 4 for all of them.
  7. Walking the parent links backward from "cog" gives hit -> hot -> dot -> dog -> cog — every step is length 1 and there are 4 of them, matching the distance found for "cog".
  8. Walking the parent links backward from "cog" gives hit -> hot -> lot -> log -> cog — every step is length 1 and there are 4 of them, matching the distance found for "cog".
  9. Both sequences reach "cog" in exactly 4 steps (5 words) because both branch off the same shared prefix "hit" -> "hot" before splitting at the fork where two different words are one letter from the next stop. RETURN both.

Now solve it yourself

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

Solve Word Ladder II in the editorAll Graph problemsBack to roadmap