Word Ladder
You get two words, beginWord and endWord, and a list of words wordList. A ladder starts with beginWord, ends with endWord, and changes exactly one letter from each word to the next. Every word after beginWord must come from wordList, so endWord must be in it; beginWord need not be.
Return the number of words in the shortest ladder, counting both ends, or 0 if there is none.
Function
- beginWordstring
- the first word of the ladder
- endWordstring
- the word the ladder must reach
- wordListstring-array
- the words every later step must come from
- Returnsinteger
- the number of words in the shortest ladder, or 0 if there is none
Constraints
1 ≤ beginWord.length ≤ 10endWordand every word inwordListhave the same length asbeginWord.1 ≤ wordList.length ≤ 5000- All words hold only lowercase English letters.
beginWord != endWord- The words in
wordListare all different.beginWordmay or may not be one of them.
Examples
- Input
- beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
- Output
- 4
- Explanation
leadandgolddiffer in three letters, so a ladder needs at least 4 words, andlead,load,goad,goldhas 4.lendandlewdare dead ends.
- Input
- beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
- Output
- 0
- Explanation
cat,cot,coggets within one letter ofdog, butdogis not in the list, so no ladder can end there.
- Input
- beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
- Output
- 3
- Explanation
ab,ad,cdandab,cb,cdboth take 3 words.abis also in the list, but the start is counted once.
Follow-up
Can you return one shortest ladder itself, the words in order, instead of its length?
Hints
Open them one at a time. Each one gives away a little more.
Picture every word as a point, and draw a line between two words that differ in exactly one letter. What is a ladder in that picture, and what is the shortest one?
The shortest ladder is the path with the fewest lines, and every line counts the same. Breadth-first search reaches all words one step away before any word two steps away, so the first time it reaches
endWordit has used the fewest steps. Mark a word as visited the moment you first reach it.Comparing a word with the whole list to find its neighbours is slow. Instead, hide one letter at a time:
hot,hatandhitall becomeh*t. Put every word into the bucket of each of its patterns. The neighbours of a word are the other words in its buckets. Run the search level by level frombeginWordand count the levels.
Solution
Treat the words as nodes of a graph, with an edge between words one letter apart. Every edge costs the same, so breadth-first search finds the shortest ladder. The hard part is finding the edges fast. Below, n is the number of words and L their length.
Try every ladder with depth-first search
Correct, but does not finish on the largest tests
Intuition
From the current word, try every unused word one letter away and go deeper, keeping the length when you reach endWord. Mark words on the path as used, and free them as you back out. Once a ladder of best words exists, stop extending paths of best-1 words.
This tries every ladder without a repeated word, and a shortest ladder never repeats one: cutting out the part between two copies would shorten it.
The 26 words aaa, baa up to zaa are all one letter apart and can be ordered in about 4 × 10^26 ways. If endWord is unreachable, the cut never fires and the search tries them all.
Algorithm
- Mark
beginWordused if it is in the list, and setbestto 0. search(word, length): atendWord, keeplengthif it beatsbest, and return. Ifbestis set andlength + 1 ≥ best, return.- Otherwise, for each unused word one letter away, mark it, call
search(next, length + 1), and unmark it. - Return
bestaftersearch(beginWord, 1).
def ladderLength(beginWord, endWord, wordList):
def one_letter_apart(a, b):
differences = 0
for x, y in zip(a, b):
if x != y:
differences += 1
if differences > 1:
return False
return differences == 1
best = 0 # words in the shortest sequence found so far, 0 while there is none
used = [word == beginWord for word in wordList] # words on the current path
def search(word, length):
nonlocal best
if word == endWord:
if best == 0 or length < best:
best = length
return
if best != 0 and length + 1 >= best:
return # any longer path cannot beat the best one
for i, candidate in enumerate(wordList):
if not used[i] and one_letter_apart(word, candidate):
used[i] = True
search(candidate, length + 1)
used[i] = False # free the word for other paths
search(beginWord, 1)
return bestBreadth-first search, comparing every pair
Correct, but does not finish on the largest tests
Intuition
A queue explores the words in order of distance: all words at distance d leave it before any word at distance d + 1. So when a word is first reached at distance d, every closer word has already been explored, and a shorter ladder to it would have reached it earlier. Its distance is final the moment it joins the queue, so mark it visited then, and the first time endWord turns up, its distance is the answer.
This version finds a word's neighbours by comparing it with every word in the list, stopping at the second difference: O(n² × L), up to 25 million word comparisons for 5,000 words.
Algorithm
- If
endWordis not inwordList, return 0. - Queue
beginWordwith length 1, marked visited if it is in the list. - Take the next word and compare it with every unvisited word. For each one letter away: if it is
endWord, return length + 1; otherwise mark it and queue it with length + 1. - If the queue runs empty, return 0.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
def one_letter_apart(a, b):
differences = 0
for x, y in zip(a, b):
if x != y:
differences += 1
if differences > 1:
return False
return differences == 1
if endWord not in wordList:
return 0
visited = [word == beginWord for word in wordList]
queue = deque([(beginWord, 1)]) # (word, words in the sequence up to it)
while queue:
word, length = queue.popleft()
# Compare against every word to find the neighbours.
for i, candidate in enumerate(wordList):
if not visited[i] and one_letter_apart(word, candidate):
if candidate == endWord:
return length + 1
visited[i] = True
queue.append((candidate, length + 1))
return 0Breadth-first search with wildcard buckets
Intuition
Two words are one letter apart exactly when hiding the same position makes them equal: hot and hit both become h*t. Give every word L patterns, one per hidden position, and add it to a bucket for each. A word's neighbours are the other words in its L buckets, found by L hash lookups instead of a pass over the list.
In the first example, l*ad holds load and le*d holds lend and lewd, so level 2 is those three; *oad then gives goad, and go*d gives gold at level 4.
Once a bucket is scanned, every word in it is reached, so empty it: the 26-word bucket *aa is scanned once, not 26 times. The cost is O(n × L²) time and space, about 500,000 letter steps for 5,000 words of 10 letters.
Algorithm
- If
endWordis not inwordList, return 0. - Bucket every word,
beginWordincluded, under each of itsLpatterns. - Queue
beginWord, marked visited, at length 1. - For each word of a level: at
endWord, return the length. Otherwise move every unvisited word in each of its pattern buckets to the next level, mark it visited, and empty the bucket. - Add 1 to the length per level. If the queue runs empty, return 0.
from collections import defaultdict, deque
def ladderLength(beginWord, endWord, wordList):
if endWord not in wordList:
return 0
size = len(beginWord)
# "h*t" -> every word that matches it: hot, hat, hit... are one letter apart.
buckets = defaultdict(list)
for word in set(wordList) | {beginWord}:
for i in range(size):
buckets[word[:i] + "*" + word[i + 1:]].append(word)
visited = {beginWord}
queue = deque([beginWord])
length = 1 # words in the sequence up to the current level
while queue:
for _ in range(len(queue)): # one level: every word at this distance
word = queue.popleft()
if word == endWord:
return length
for i in range(size):
pattern = word[:i] + "*" + word[i + 1:]
for neighbour in buckets[pattern]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
buckets[pattern] = [] # all of them are visited now: never scan it again
length += 1
return 0
Pitfalls and edge cases
- Counting changes instead of words.
leadtogoldis 3 changes and 4 words; the answer is 4. - Skipping the check that
endWordis inwordList. The second example reachescog, one letter fromdog, but the answer is 0. - Marking a word visited when it leaves the queue. A word in the bucket
*aacan then join up to 25 times, and the queue grows far pastn. - Recursing along the ladder. A shortest ladder can be thousands of words long, enough to overflow the call stack.
Frequently asked questions3
What is the time complexity of Word Ladder?
With wildcard buckets it is O(n × L²) for n words of length L: each word has L patterns of L letters. Comparing every pair of words costs O(n² × L), and trying every ladder with depth-first search is exponential.
How do you find the words that are one letter away?
Wildcard buckets are one way. The other is to change each position to each of the 26 letters and look the result up in a hash set of the words: 26 × L lookups of L letters per word, O(n × 26 × L²) in total. Both beat a pass over the list.
Can bidirectional BFS make Word Ladder faster?
Yes. Search from both ends at once, always growing the smaller side by one level, and stop when the two sides meet. With about b neighbours per word and d changes, one search can touch about b^d words; two that meet in the middle touch about 2 × b^(d/2).
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def ladderLength(beginWord, endWord, wordList):
# Write code hereTest #1
Test #2
Test #3
Arguments
beginWord = "lead" endWord = "gold" wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Expected Output
4