The problem
Change a start word into an end word by changing one letter at a time, where every in-between word must be in the dictionary. Return the number of words in the shortest such chain (0 if impossible).
Input: start "hit", end "cog", dictionary [hot, dot, dog, lot, log, cog] Output: 5 (hit → hot → dot → dog → cog)
Picture it
Picture each word as a stepping stone, and two stones are connected when the words differ by exactly one letter. From the start word we explore in waves: all words one change away, then all words two changes away, and so on. The first wave that contains the end word gives the shortest chain.
How to recognise it
- You move from one item to another by a small, fixed kind of change (here, one letter), and only some results are allowed (words in a list).
- The question asks for the fewest steps, and every step costs the same.
- The graph is never given: you can generate the neighbours of any item on demand.
- With up to 5,000 words of length up to 10, you want something close to linear in the number of words.
Start with brute force
Run a breadth-first search, but find each word's neighbours by comparing it with every word in the list and keeping those that differ in exactly one position.
def ladder_brute(begin, end, words):
def one(a, b):
return sum(x != y for x, y in zip(a, b)) == 1
seen, q = {begin}, deque([(begin, 1)])
while q:
w, d = q.popleft()
if w == end:
return d
for x in words:
if x not in seen and one(w, x):
seen.add(x)
q.append((x, d + 1))
return 0
Each word that is expanded is compared with all N words, each comparison costing L letters, so time is O(N²·L): for N = 5,000 and L = 10 that is about 2.5 × 10^8 letter comparisons. Space is O(N·L).
From brute force to the idea
- Find the waste. Comparing a word with every other word is mostly wasted, because a word of length L has at most 25·L possible one-letter neighbours, and most of them are not words.
- Generate instead of compare. For each position i and each letter from
atoz, buildnxt = w[:i] + ch + w[i+1:]and testnxt in words. A set makes the test O(1) on average. - BFS gives the shortest chain. Every word in the queue at one level is the same number of changes from
begin, so the first timeendis popped,stepsis the answer, counted in words (the start word counts as 1). - Remove words as you queue them.
words.remove(nxt)turns the set into the visited marker: a word reached first at this level can never be reached sooner later, so a second visit is pointless. - Count levels, not words.
steps += 1runs once after the whole level has been processed.
The key idea: build neighbours by changing one letter, look them up in a set, and let BFS find the shortest chain.
The key idea
BFS over words (neighbours = one-letter changes found in the dictionary). The first time you reach the end word is the shortest.
Python solution
def ladder_length(begin, end, words):
words, q, steps = set(words), deque([begin]), 1
while q:
for _ in range(len(q)):
w = q.popleft()
if w == end:
return steps
for i in range(len(w)):
for ch in "abcdefghijklmnopqrstuvwxyz":
nxt = w[:i] + ch + w[i + 1:]
if nxt in words:
words.remove(nxt); q.append(nxt)
steps += 1
return 0LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(N²·L): each expanded word is compared with all N words | O(N·L): the word list and a seen set |
| Generate neighbours (shown code) | O(N·L·26·L): each word tries 26·L candidates, and each candidate costs O(L) to build and hash | O(N·L): the set of words and the queue |
For N = 5,000 and L = 10 the shown code needs roughly 1.3 × 10^7 character operations.
Edge cases
- No chain exists (the end word is missing from the list, or unreachable): returns 0.
- Start equals end: returns 1, since the first popped word is already the end.
- The start word is not in the list: fine, because it is only queued, never looked up.
- The start word is in the list: also fine. It can be queued once more, but all its neighbours are gone by then, so the answer is unchanged.
- The input list is not changed:
set(words)makes a copy, so the caller's list keeps all its words. - All words must have the same length. The code does not check this.
Common mistakes
- Returning the number of changes (steps − 1) instead of the number of words in the chain.
- Not marking visited words, so the search revisits words and may loop forever.
- Using a list for the dictionary, so each
intest is O(N). - Using DFS, which finds a chain but not necessarily the shortest one.
- Incrementing
stepsper word popped instead of per level.
Return one shortest chain itself as a list of words, from the begin word to the end word, or an empty list if there is none. Describe what changes, then write it if you like.
Compare with our answer
Keep the same BFS, but remember for each word where it came from. A dictionary of parents serves as both the visited marker and the way to walk back from the end word.
def ladder_path(begin, end, words):
words = set(words)
parent, q = {begin: None}, deque([begin])
while q:
w = q.popleft()
if w == end:
path = []
while w is not None:
path.append(w)
w = parent[w]
return path[::-1]
for i in range(len(w)):
for ch in "abcdefghijklmnopqrstuvwxyz":
nxt = w[:i] + ch + w[i + 1:]
if nxt in words and nxt not in parent:
parent[nxt] = w
q.append(nxt)
return []
Time O(N·L²·26) as before, space O(N·L).
A strong answer mentions: recording a parent when a word is first queued, walking back from the end word and reversing the result, and that BFS still guarantees the shortest chain.
1. A 4-digit combination lock starts at 0000. One move turns a single wheel one step up or down (9 wraps to 0), and some codes are dead ends that must be avoided. You need the fewest moves to a target code. Which approach fits best?
States are lock codes, a move is one step in an implicit graph, and every move costs the same, so BFS finds the fewest moves. The edit distance and the greedy rule ignore the dead ends.
2. Why does the shown code call words.remove(nxt) when it queues a word?
A word first reached at some level cannot be reached in fewer steps later, so removing it from the set prevents repeats and keeps the work bounded. Removing it has nothing to do with sorting.
3. A learner moves steps += 1 inside the for _ in range(len(q)) loop, so it runs once per word popped. Which input still returns the right answer?
The chain hit, hot, dot, dog has one word per level, so counting words and counting levels agree. In each other input some level holds two words (such as hot and hat), so counting per word gives too large a number.
Score 60% or more and the lesson is marked complete.