Word Ladder
WHAT IT SAYS
Transform a start word into an end word, one letter at a time, with every intermediate word in the dictionary; find the shortest transformation length.
WHAT IT'S REALLY ASKING
"Words are nodes; a one-letter difference is an edge; the dictionary is an unweighted graph that nobody drew for you. 'Shortest transformation' is then just BFS — the only real work is generating edges without comparing every pair of words: mutate the current word letter by letter through the alphabet and let the dictionary answer 'is this a node?'"
DFS through transformations, minimising over complete paths
Exponential — paths through the word graph multiplyRecursively try every one-letter mutation that lands in the dictionary, tracking the current chain length and the best complete chain found; backtrack and explore alternatives exhaustively.
WHERE THE WORK IS WASTED — DFS answers 'shortest' by enumerating ALL paths and taking the minimum — it commits to a route, follows it possibly hundreds of words deep, then unwinds to try the next, revisiting the same intermediate words along countless different chains. But shortest-path in an UNWEIGHTED graph never requires seeing two paths to the same node: the first arrival, in breadth order, is provably minimal, and every later arrival is discardable on contact. The exponential blowup is the price of using a depth tool on a breadth question — the search order, not the search, is the bug.
Build edges by mutation, not comparison. Then just BFS.
Three stacked decisions, each with its own argument. First, recognise the implicit graph. Nothing in the input says 'graph' — it says words and a rule. But the rule ('differ in one letter') is a symmetric relation on dictionary words, which IS an undirected edge set, and 'shortest sequence of applications' IS shortest path. Unweighted shortest path has exactly one right tool: BFS, whose level order guarantees first-arrival-is-minimal. Levels are ladder lengths; when the end word surfaces, its level is the answer, no further search justified. Second, the edge-generation economy — the part that actually decides your complexity. Materialising the graph by comparing all word pairs costs O(n² · L): ten thousand words means fifty million comparisons before the search even starts. Invert it: from the CURRENT word, generate every candidate neighbour directly — L positions × 25 alternative letters = 25·L mutations — and test each against a hash set of the dictionary in O(1). Cost per node: O(L² ) (each mutation is an L-char string), total O(n · L²), and crucially it scales with words VISITED, not pairs EXISTING. When the alphabet is small and words are short, generate-and-test beats compare-all-pairs; the dictionary's only job is membership. (The wildcard-bucket preprocessing — grouping words by patterns like 'h*t' — is the same idea run in reverse, trading memory for per-node speed.) Third, the visited discipline with a twist that only works for distances: DELETE each word from the dictionary set the moment it is enqueued. Deletion is marking-visited fused with the membership test — a deleted word fails future lookups, so no word is ever enqueued twice, and no separate visited set exists. Why is discarding safe? Because the first enqueue happens at the word's minimal level, and for a shortest-DISTANCE question no later, longer arrival can ever matter. (Hold that thought: Word Ladder II, which wants the paths themselves, is exactly where this aggressive deletion breaks — same-level arrivals must survive there.)
BFS with mutate-and-lookup, deleting on enqueue
O(n · L²) time with the set, O(n) queue and set spaceLoad the word list into a hash set; if the end word is absent, return 0 immediately. Queue the start word at level 1. Per dequeued word: for each position, for each letter a-z, form the mutation; if it equals the end word, return level + 1; if it is in the set, delete it and enqueue at level + 1. Empty queue: return 0. Bidirectional BFS (expand the smaller frontier from both ends) cuts the search space roughly to its square root when the graph is large.
Implicit Graph, Explicit BFS
YOU'LL SEE IT AGAIN WHEN
- States and a mutation rule are given instead of nodes and edges — the graph exists but was never drawn.
- The question is MINIMUM steps/moves/transformations — unweighted shortest path, demanding breadth order, not depth.
- Neighbours are cheaper to GENERATE (apply each possible move) than to FIND (compare against all states) — small move-alphabet, hash-set membership.