How do you solve the word ladder problem?

Q: How do you solve the word ladder problem?

**Target Audience:** Beginners preparing for coding interviews — you know Python strings, sets and dicts; graph search is explained from scratch. **Difficulty:** Hard **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every output shown was produced by actually running the code with `python3` (3.13); nothing is typed in by hand. ## 1. Why This Even Matters — A Story First Lewis Carroll published this puzzle in 1879 as "Doublets": turn one word into another by changing **one letter at a time**, and every step must be a real word. His own example turns HEAD into TAIL: HEAD → HEAL → TEAL → TELL → TALL → TAIL ([Wikipedia: Word ladder](https://en.wikipedia.org/wiki/Word_ladder)). Try it by hand and you quickly notice you are exploring: from HEAD you could go to HEAL, HEAP, HEAR, READ, BEAD… and from each of those to many more. Wandering down on

The problem

Question presented to candidate: "Given a begin word, an end word and a list of dictionary words, find the number of words in the shortest transformation sequence from begin to end, where each step changes exactly one letter and every intermediate word must be in the list. Return 0 if there is no such sequence. Please code it in Python."

What a strong answer should cover:

Modelling: words are nodes, one-letter changes are edges, and the graph is implicit — generated on demand, not stored.
BFS because every edge has the same cost, so the first time end is reached is the shortest chain; the answer counts words, not steps.
Neighbour generation: 26 letters × L positions, kept only if the candidate is in a set; mark visited when queued (e.g. by removing from the set).
Complexity O(N · 26 · L²) time and O(N · L) space, and why comparing all pairs, O(N² · L), is worse for large N.
Python specifics: set (not list) for membership, collections.deque, string.ascii_lowercase, and the O(L) cost of word[:i] + ch + word[i+1:] because strings are immutable. Bidirectional BFS as the follow-up optimisation.

Clarifying questions expected:

Count words or steps? Must endWord be in the list?
Do you want the sequence itself, or all shortest sequences?

Code / implementation expected: Yes — a ladder_length(begin, end, word_list) in Python using BFS with a set, ideally also returning the chain via a parent map.

graphs
bfs

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you know Python strings, sets and dicts; graph search is explained from scratch. Difficulty: Hard Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every output shown was produced by actually running the code with python3 (3.13); nothing is typed in by hand.

1. Why This Even Matters — A Story First

Lewis Carroll published this puzzle in 1879 as "Doublets": turn one word into another by changing one letter at a time, and every step must be a real word. His own example turns HEAD into TAIL: HEAD → HEAL → TEAL → TELL → TALL → TAIL (Wikipedia: Word ladder).

Try it by hand and you quickly notice you are exploring: from HEAD

The solution is hidden so you can try first

15 min read · 10 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonBFS word ladder on six inputs, printing the shortest chain

Practice

PythonOne-way BFS vs bidirectional BFS: words expanded on generated dictionaries