CODING CHALLENGE · N°44

Word Ladder

Hard GraphsBFSStrings

Transform one word into another by changing a single letter at a time, where every step must be a real word. The shortest such chain is a shortest path in a hidden graph — so it is a job for breadth-first search. Return the length of the shortest ladder. Solve it in Python or TypeScript, with hidden tests.

The problem

Given a begin word, an end word, and a list of allowed words, return the number of words in the shortest transformation sequence from begin to end, changing exactly one letter at a time, where every intermediate word (and end) must be in words. Count both endpoints. Return 0 if no such sequence exists.

EXAMPLE 1

Input begin = 'hit', end = 'cog', words = ['hot','dot','dog','lot','log','cog']

Output 5

hit → hot → dot → dog → cog is 5 words

EXAMPLE 2

Input begin = 'hit', end = 'cog', words = ['hot','dot','dog','lot','log']

Output 0

end word "cog" is not in the list

CONSTRAINTS

All words have the same length and are lowercase; begin need not be in words, but end must be.
Each step changes exactly one letter and must land on a word in the list.
The answer counts words (nodes), not steps — the shortest chain of length k has k words. BFS gives the shortest.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement ladder_length(begin, end, words): BFS from begin, where a word’s neighbours are the words in the set reachable by changing one letter. Track the depth (word count); the first time you reach end, return it. Return 0 if BFS exhausts.

HINTS — 4 IDEAS

Put the word list in a set for O(1) membership. If end is not in it, the answer is 0 immediately.
BFS level by level from begin, carrying the number of words used so far (start at 1).
Neighbours of a word: for each position, try all 26 letters; keep those that are in the set and not yet visited.
The first time you dequeue end, its depth is the shortest ladder length. BFS guarantees shortest-first.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

It is a shortest-path problem on an implicit graph, so use BFS. Two words are neighbors if they differ by exactly one letter and both are in the dictionary; BFS from the start word reaches the end word in the fewest steps. Precompute neighbors with wildcard patterns (h*t groups hat, hot, hit) to avoid comparing every pair of words.

Complexity

Time O(N · L · 26) to build wildcard buckets (N words of length L); the BFS itself is O(V + E).

Common mistakes

Using DFS — it explores deep first and does not give the shortest ladder; BFS does.
Comparing every pair of words (O(N²·L)) instead of grouping by wildcard patterns.
Not marking words visited, so BFS revisits and can loop.

Where this shows up

Word ladder is BFS-for-shortest-path on a graph you generate on the fly — the same “fewest steps between states” pattern as puzzle solvers, refactor/transformation planners, and any unweighted shortest-path problem where you expand neighbors lazily rather than storing the whole graph.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA