DEV Community

Nora Vale
Nora Vale

Posted on

A Four-Letter Word Ladder Is a Tiny BFS Problem

A four-letter word ladder looks like a word game and is actually a graph problem. Words are nodes. Two words are adjacent if they differ by exactly one character. A ladder from start to target is a path. The shortest ladder is a shortest path, and shortest path in an unweighted graph has an algorithm you already know: breadth-first search.

The interesting part is the graph construction. With a dictionary of N words, checking every pair for a one-character difference is O(N² · L), which is fine for a few thousand common four-letter words and hopeless for a full dictionary. The standard trick is to bucket words by wildcard patterns. For each word, generate L patterns by replacing one position with a wildcard: CARE gives _ARE, C_RE, CA_E, CAR_. Words that share a pattern are one edit apart, so you can build adjacency from the buckets in one pass.

BFS from the start word then gives the shortest distance to every reachable word, and a parent map gives you the actual route. Two details matter in practice. First, the dictionary defines the graph, so a ladder computed against an unusual word list can be shorter than one computed against a common-word list. Second, the graph is not static: if you allow plurals and obscure forms, you get shortcuts that most players would never find, which is why honest puzzle tools should say which list they used.

The useful extension for players is not "solve it for me" but "is this word reachable at all". Running BFS from your current word to the target answers that question in milliseconds, and the answer is often yes even when you have convinced yourself the route is dead. That is a much better tool than a full solver, because it tells you whether to keep planning without telling you what to do.

I play the four-letter version at Poople Unlimited and the smallest useful version of this graph search is maybe forty lines of JavaScript. If you are teaching BFS, a word ladder is a better example than a grid maze because the data structure is the interesting part.

Top comments (0)