Pattern visualizer
Word Ladder II
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. Animated on: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] — return every shortest transformation sequence from beginWord to endWord..
BFS by whole levels builds a parent DAG; DFS backtracking reads off every shortest path
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.
1FUNCTION findLadders(beginWord, endWord, wordList):2 dict <- SET OF wordList3 IF endWord NOT IN dict RETURN []4 level <- {beginWord}5 parents <- EMPTY MAP6 WHILE level NOT EMPTY AND endWord NOT FOUND7 REMOVE EVERY WORD IN level FROM dict8 next <- EMPTY SET9 FOR EACH word IN level10 FOR EACH candidate ONE LETTER FROM word11 IF candidate IN dict12 ADD candidate TO next13 APPEND word TO parents[candidate]14 level <- next15 RETURN ALL PATHS FROM beginWord TO endWord VIA parents
← / → step · space play · Home restart