Word Ladder
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.
begin = 'hit', end = 'cog', words = ['hot','dot','dog','lot','log','cog']5begin = 'hit', end = 'cog', words = ['hot','dot','dog','lot','log']0- All words have the same length and are lowercase;
beginneed not be inwords, butendmust 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.
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.
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.
- Put the word list in a set for O(1) membership. If
endis 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.
Explore the topic
See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.