The word ladder LeetCode problem, better known as LeetCode 127, “Word Ladder,” is a staple breadth-first search interview question, and Word Ladder II, LeetCode 126, is its harder all-paths sibling. Poople takes the exact same puzzle and turns it into a live daily game: change a start word into POOP one real word at a time. This post walks through both LeetCode problems in Python, explains the breadth-first search that solves each one, and then shows how Poople solves the identical graph problem in production, using a couple of shortcuts the generic LeetCode problem is never allowed to take. If word ladders are new to you, start with the basics before diving into the code.
The Word Ladder LeetCode Problem (127)
LeetCode 127, titled Word Ladder, states the problem precisely: given a beginWord, an endWord, and a wordList of allowed words, return the number of words in the shortest transformation sequence from beginWord to endWord, counting both endpoints, or return 0 if no such sequence exists. LeetCode’s own wording for the target is a shortest transformation sequence, and that phrase is worth remembering, because it names exactly what the algorithm has to compute: the length of the shortest path between beginWord and endWord.
Two rules keep the search well defined. First, each step in the sequence can change exactly one letter, so hot can become hit, but not heat, in a single move. Second, every intermediate word in the sequence, along with endWord itself, must appear in wordList. If endWord is missing from wordList, the answer is immediately 0, since there is nowhere for a valid sequence to end.
Framed this way, the word ladder problem stops looking like a wordplay puzzle and starts looking like a graph problem. Treat every word as a node. Draw an edge between two nodes whenever the two words differ by exactly one letter. Every edge in that graph costs the same single step, so the graph is unweighted, and finding the shortest transformation sequence is exactly the same task as finding the shortest path between two nodes in an unweighted graph. That framing points straight at the right algorithm: breadth-first search visits nodes in order of distance from the start, so the first time it reaches endWord, it has necessarily arrived by the shortest possible route. A depth-first search would eventually find some path too, but it could easily wander down a long detour first, with no guarantee that the first path it finds is the shortest one.
Solving Word Ladder with BFS in Python
The Python solution below solves LeetCode 127 directly, and it is a fairly typical word ladder Python implementation: a queue drives the search outward, and a set tracks which words have already been visited.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
words = set(wordList)
if endWord not in words:
return 0
queue = deque([(beginWord, 1)])
seen = {beginWord}
while queue:
word, steps = queue.popleft()
if word == endWord:
return steps
for i in range(len(word)):
for c in "abcdefghijklmnopqrstuvwxyz":
nxt = word[:i] + c + word[i + 1:]
if nxt in words and nxt not in seen:
seen.add(nxt)
queue.append((nxt, steps + 1))
return 0
The queue holds pairs of a word and the number of steps taken to reach it, seeded with (beginWord, 1) since beginWord itself counts as the first word in the sequence. Each iteration pops the oldest entry, the property of a queue that keeps a breadth-first search expanding in strict order of distance, checks whether that word is endWord, and if not, generates every neighbor by trying all 26 letters at each position in the word. A neighbor only gets pushed onto the queue if it is both a legal word, meaning it is present in the words set, and unvisited, meaning it is not already in seen; that second check stops the search from looping back over words it has already explored and keeps it moving strictly outward, layer by layer. When the popped word equals endWord, its recorded step count is the length of the shortest transformation sequence, and the function returns it right away.
The seen set doubles as the fix for a common early bug: without it, the queue would revisit the same word from multiple neighbors, and the search would never terminate on a graph with cycles, which a word graph always has. Converting wordList into a set up front matters just as much for performance, since checking membership in a Python list costs O(n), while a set lookup costs O(1).
Neighbor generation is the part of this word ladder solution that is easy to get wrong on a whiteboard, though it is not actually complicated: for a word of length L, the code tries L positions and 26 candidate letters at each position, so building and checking neighbors costs O(L times 26) string operations per word. Across N words in the wordList, the whole search costs roughly O(N times L times 26) in the worst case, since BFS visits each word at most once. For LeetCode’s usual test sizes that is fast, but for a much larger wordList, a common optimization is bidirectional BFS: run the search outward from both beginWord and endWord at once, alternating which side expands, and stop as soon as the two frontiers meet. Because the number of nodes a breadth-first search touches tends to grow with the branching factor raised to the depth, searching from both ends and stopping halfway can visit dramatically fewer nodes than searching the full distance from one end.
Word Ladder II (126): Every Shortest Path
LeetCode 126, Word Ladder II, asks a bigger question than 127. Instead of the length of one shortest transformation sequence, it wants every shortest transformation sequence, each one returned as a full list of words from beginWord to endWord.
The natural instinct is to reach for plain backtracking from beginWord, trying every legal one-letter change and recursively exploring from there. That finds paths, but it does not solve problem 126, for two reasons. First, a naive depth-first search has no notion of which paths are shortest; it will happily wander down routes that are far longer than necessary before backtracking, and filtering those out afterward wastes enormous amounts of work once the graph has any real size. Second, even restricted to short paths, a plain depth-first search can revisit the same word along different branches with no way to know it has already found every shortest route through that word, so the same work ends up repeated many times over.
The fix is to combine BFS with a parents map. Run breadth-first search outward from beginWord one layer at a time, but instead of recording just one predecessor for each newly discovered word, record every word in the previous layer that reaches it. A word can have several different neighbors one layer closer to beginWord, and every one of those neighbors sits on some shortest path, so all of them need to be kept rather than just the first one found. Once the layer containing endWord has been fully processed, the parents map holds enough information to reconstruct every shortest path, and the search can stop, since no path discovered in a later layer could possibly be shorter.
from collections import defaultdict
def findLadders(beginWord, endWord, wordList):
words = set(wordList)
if endWord not in words:
return []
parents = defaultdict(set) # word -> set of words that reached it one step earlier
frontier = {beginWord}
found = False
while frontier and not found:
next_frontier = defaultdict(set)
for word in frontier:
for i in range(len(word)):
for c in "abcdefghijklmnopqrstuvwxyz":
nxt = word[:i] + c + word[i + 1:]
if nxt in words:
next_frontier[nxt].add(word)
words -= set(next_frontier) # drop this layer so we only keep shortest edges
for nxt, preds in next_frontier.items():
parents[nxt] |= preds
if nxt == endWord:
found = True
frontier = set(next_frontier)
if not found:
return []
paths = []
def backtrack(word, suffix):
if word == beginWord:
paths.append([beginWord] + suffix)
return
for pred in parents[word]:
backtrack(pred, [word] + suffix)
backtrack(endWord, [])
return paths
This function builds that parents map layer by layer with a frontier set, following the pattern above, then reconstructs paths with backtrack, which walks from endWord back to beginWord through the parents map, branching every time a word has more than one recorded predecessor. Removing each new layer’s words from the words set, the line words -= set(next_frontier), matters just as much here as the seen set does in problem 127: skip it, and the BFS can wire a word to a predecessor from a layer that is not actually one step closer, corrupting the parents map with edges that never sit on a shortest path.
The backtrack function above is written recursively because that is the clearest way to read it: it walks from endWord to beginWord, and at every word with multiple parents, it branches into multiple calls. Poople’s production solver reconstructs paths through the same kind of parents map, but does it with an explicit stack instead of recursive function calls, an iterative depth-first search rather than a recursive one. The output is identical either way; the difference is that an explicit stack cannot overflow the call stack no matter how deep or how heavily branching the graph gets, which starts to matter once the parents map is built from a real dictionary instead of a handful of test words.
How Poople Solves the Same Problem in Production
Poople is a live daily word ladder game where the target word is always POOP, played over a dictionary of 2,398 four-letter words. Every day’s puzzle hands players a different start word, and the job is to reach POOP one real word at a time, the same rules as LeetCode 127 and 126, just running on real players instead of test cases.
The word ladder solver tool on the site is, almost line for line, the Word Ladder II idea above put into production: a multi-parent, layer-by-layer BFS builds a parents map exactly the way the Python code does, then an iterative depth-first backtracking pass, using an explicit stack rather than recursion, walks that map to rebuild every shortest path between any two words a player types in. The result is capped at 20 paths, for the same reason problem 126 needs a cap on large inputs: a heavily connected word graph can have far more shortest paths than are useful to look at on a single page.
Where Poople’s production solver pulls ahead of a straightforward LeetCode submission is in what it does not have to compute at play time. LeetCode’s endWord changes with every test case, so nothing about problem 127 or 126 can be precomputed ahead of time; the BFS has to run fresh for every input. Poople’s target never changes: it is POOP, every single day. That fixed endpoint means Poople can run the BFS exactly once, offline, starting from POOP and expanding outward across the whole dictionary, recording each word’s distance back to POOP. That distance is the puzzle’s par, and across the full dictionary it ranges from 0, for POOP itself, up to 11 for the hardest starting words.
With par precomputed and stored as plain data, solving a puzzle at play time no longer needs a live BFS at all. The solver looks at the current word, checks its neighbors, and steps to any neighbor whose par is exactly one lower than the current word’s par; repeating that from the new word walks a guaranteed shortest path all the way to POOP. That greedy descent costs O(L times 26) per step, the same neighbor-generation cost as the code above, but it never runs a search, because the precomputed par table already encodes the entire graph’s distances back to POOP. The engineering write-up on how Poople was built goes deeper into that par table, the daily puzzle math, and the rest of the word graph behind the game.
Pitfalls and Optimizations
A handful of details separate a working word ladder LeetCode solution from one that is slow, or quietly wrong.
Remove words from the candidate set once a layer has consumed them, rather than only checking a seen set on the way in. The 126 solution above does this with words -= set(next_frontier); skip it, and a word can get wired to a predecessor from a layer that is not actually one step closer, corrupting the parents map with edges that are not on any shortest path.
Generate neighbors by substituting one position at a time and trying all 26 letters, rather than comparing every pair of words in wordList directly. Comparing every pair costs O(N squared) and stops scaling quickly, while position substitution costs O(L times 26) per word no matter how large the dictionary gets. For very large word lists, some solutions go further and bucket words by wildcard patterns, replacing one letter of a word with a placeholder to get patterns like p*op, so finding neighbors becomes a dictionary lookup instead of trying all 26 letters at every position.
For problem 127, bidirectional BFS is the highest-value optimization once wordList gets large: searching from beginWord and endWord at the same time and stopping when the two frontiers meet can cut the number of explored nodes dramatically compared to searching the full distance from one end.
For problem 126, favor iterative backtracking over recursive backtracking once the parents map comes from a real dictionary rather than a handful of test words. Poople’s solver makes exactly this choice, using an explicit stack instead of recursive calls, which removes any risk of a stack overflow on a large, heavily branching word graph.
Frequently Asked Questions
What algorithm solves the LeetCode Word Ladder problem?
Breadth-first search solves it, because BFS finds the shortest path in an unweighted graph, and the word ladder problem is exactly that: words are nodes, and a one-letter change between two words is an edge.
What is the difference between LeetCode 127 and 126?
LeetCode 127 asks for the length of one shortest transformation sequence between beginWord and endWord. LeetCode 126, Word Ladder II, asks for every shortest transformation sequence, each returned as a full list of words.
How do you solve Word Ladder II?
Run a breadth-first search outward from beginWord one layer at a time, recording every predecessor word that first reaches each new word, then backtrack through that parents map from endWord to beginWord to rebuild every shortest path.
Where can I try a word ladder for real?
Play Poople, a free daily word ladder, and use the word ladder solver to see every shortest path between any two four-letter words.
Try a Word Ladder Yourself
Reading the word ladder LeetCode algorithm is one thing; watching it run on real words is another. Try the word ladder solver on any two four-letter words to see every shortest path between them, or play Poople to work through a fresh word ladder to POOP today. For more on the engineering behind the game, including the par table and the daily puzzle math, read how Poople was built.