Example 1
ready- Input
beginWord = "hit" endWord = "cog" wordList = [ "hot", "dot", "dog", "lot", "log", "cog" ]- Expected
5- Why
- one shortest sequence is hit → hot → dot → dog → cog
Word Ladder
50 min · ladderLength()Changing one letter can turn cold into cord. A few careful changes can turn it into
warm — but every word along the way has to be approved.
Given beginWord, endWord, and a unique wordList, transform the beginning word by
changing exactly one letter at a time. Every word after beginWord, including
endWord, must appear in wordList.
Return the number of words in the shortest valid sequence, counting both ends. Return
0 when no sequence exists.
Ground rules:
- Every word has the same length and uses lowercase English letters.
beginWorddoesn't have to appear inwordList.endWordmust appear inwordListfor any sequence to be valid.- When
beginWord == endWordand that word is in the list, the answer is1.
Constraints
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5_000- Every
wordList[i]has the same length asbeginWord. - All words contain only lowercase English letters.
- Words in
wordListare unique.
Hints
Turn words into states
Two words are neighbors when they differ at exactly one position. A shortest path through those neighbor links is the transformation you want.
Avoid comparing every pair
cold can be represented by patterns such as *old, c*ld, co*d, and col*.
Words sharing one of those patterns differ in at most the hidden position.
Search by sequence length
Start breadth-first search at beginWord with length 1. Mark a word when you add it
to the queue, so two patterns can't schedule the same word twice.
Follow-up
How would a search growing from both beginWord and endWord reduce the work when the
dictionary is large and the shortest ladder is deep?
Visible cases
Examples
Example 2
ready- Input
beginWord = "hit" endWord = "cog" wordList = [ "hot", "dot", "dog", "lot", "log" ]- Expected
0- Why
- cog is absent from the dictionary, so no valid sequence can end there
Example 3
ready- Input
beginWord = "same" endWord = "same" wordList = [ "same", "came" ]- Expected
1- Why
- the starting word already equals the listed ending word
Interview signal
Asked at
AmazonGoogleMetaLinkedIn
Build the word graph pair by pair
The word graph has one word per node and an edge between two words that differ in exactly one position. Build that graph by comparing every pair, then run state-space BFS, breadth-first search where the current word is the state.
from collections import deque
def ladder_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
if end_word not in word_list:
return 0
if begin_word == end_word:
return 1
words = [begin_word] + [word for word in word_list if word != begin_word]
graph = [[] for _ in words]
for left in range(len(words)):
for right in range(left + 1, len(words)):
differences = sum(a != b for a, b in zip(words[left], words[right]))
if differences == 1:
graph[left].append(right)
graph[right].append(left)
target = words.index(end_word)
queue = deque([(0, 1)])
seen = {0}
while queue:
word_index, length = queue.popleft()
if word_index == target:
return length
for neighbor in graph[word_index]:
if neighbor not in seen:
seen.add(neighbor)
queue.append((neighbor, length + 1))
return 0Time O(N²L) to compare N words of length L. Space O(N²) for the explicit
adjacency lists in the conservative worst case.
Wildcard-bucket state-space BFS
Pairwise comparison asks the wrong lookup question. A wildcard pattern replaces one
letter with *, grouping words that match everywhere else. hot and dot both belong
to *ot, so that bucket reveals their edge directly.
Build all L patterns for every dictionary word and for beginWord. During BFS, look
up the current word's patterns and enqueue unseen words from those buckets. Clear a
bucket after expanding it; a later visit can't discover anything new there.
from collections import defaultdict, deque
def ladder_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
dictionary = set(word_list)
if end_word not in dictionary:
return 0
if begin_word == end_word:
return 1
patterns: dict[str, list[str]] = defaultdict(list)
words = list(word_list)
if begin_word not in dictionary:
words.append(begin_word)
for word in words:
for index in range(len(word)):
pattern = word[:index] + "*" + word[index + 1:]
patterns[pattern].append(word)
queue = deque([(begin_word, 1)])
seen = {begin_word}
while queue:
word, length = queue.popleft()
for index in range(len(word)):
pattern = word[:index] + "*" + word[index + 1:]
for neighbor in patterns[pattern]:
if neighbor == end_word:
return length + 1
if neighbor not in seen:
seen.add(neighbor)
queue.append((neighbor, length + 1))
patterns[pattern].clear()
return 0Each word creates L buckets, and a bucket can hold at most 26 unique lowercase words
because only the hidden letter varies. With L <= 10, key construction also fits inside
that alphabet bound.
Time O(N·L·26) for bucket construction and expansion. Space O(NL) for the bucket entries, queue, and visited words.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
5
Run: visible + custom · Submit: full suite