Problem overview
The method ladderLength receives a beginWord, an endWord and a list of words, words. It returns the number of words in the shortest sequence that starts at beginWord and ends at endWord, where each step changes exactly one letter and every word after the first must be in words. It returns 0 if there is no such sequence. All words have the same length and use lowercase letters.
For beginWord = "hit", endWord = "cog" and words = ["hot", "dot", "dog", "lot", "log", "cog"], the shortest sequence is hit -> hot -> dot -> dog -> cog, which has 5 words, so the answer is 5. If "cog" is missing from the list, the answer is 0.
Approach: a shortest path in an implicit graph
Think of every word as a node, and connect two words when they differ in one letter. The question becomes the length of the shortest path between two nodes, which breadth-first search (BFS) solves: it visits all words one step away, then all words two steps away, and so on, so the first time it reaches the target the path is shortest.
Two ideas make this version fast.
Wildcard patterns find neighbours quickly
Comparing a word with every other word to find its neighbours is slow. Instead, replace one letter with * to make a pattern. hot gives *ot, h*t and ho*. Two words differ in exactly one position if they share a pattern: hot, dot and lot all have *ot. A dictionary from each pattern to its words, built once, lists a word's neighbours in a few lookups.
Searching from both ends
A normal BFS from beginWord grows wider with every level. The lesson runs one BFS from beginWord and another from endWord, and stops when they touch. Each search only needs to go about half the distance, so far fewer words are visited. The code always grows the side with the smaller current level, which keeps the work small.
Each side keeps a dictionary of distances. A distance counts words, including the starting word, so beginMinDist[beginWord] and endMinDist[endWord] both start at 1. When one side is about to visit a word that the other side has already reached, the sequence length is the sum of the two distances. No word is counted twice, because the two words that touch are different words.
Step by step
- Reject an impossible target. If
endWordis not inwords, return 0 at once. The second search starts fromendWordand relies on it being in the graph. - Write
getStarWord(word, i). It returnswordwith the letter at indexireplaced by*, built from the slicesword[:i]andword[i + 1:]. - Write
buildGraph(words). For each word and each position it computes the pattern and appends the word to that pattern's list. It returns the dictionary. - Set up both searches. Create the queues
beginQueueandendQueueas deques, the dictionariesbeginMinDistandendMinDist, put each starting word in its own queue and give it distance 1. - Write
processLevel. It expands one whole BFS level of one side: it removes every word that is in the queue now, finds its neighbours through the patterns, and returns a sequence length if a neighbour was reached by the other side. Otherwise it records each unseen neighbour with distance one more and adds it to the queue for the next level. It returns 0 when this level found no meeting. - Loop while both queues have words. Each turn expands the side whose queue is shorter, with the begin side first on a tie. If the call returns a nonzero value, return it.
- Return 0 after the loop. One side ran out of words before the searches met, so no sequence exists.
Why whole levels, and why the begin side goes first
Expanding a whole level at a time matters. If the searches advanced one word at a time, they could meet through a longer path while a shorter one was still waiting in a queue. Whole levels make the first meeting the shortest one. The loop for _ in range(len(queue)) takes the size once, so words added during the call wait for the next call.
Ties go to the begin side, with <=. The word beginWord does not have to be in words, and if it is not, the end side can never step onto it, so only the begin side's first expansion connects it to the rest. With beginWord = "hot", endWord = "dot" and words = ["dot"], a strict < would expand the end side first, find nothing and return 0. The reference returns 2.
The example
For the first example, the search goes: the begin side expands hit and reaches hot (distance 2). The queues are equal in size, so it expands again, from hot, and reaches dot and lot (distance 3). Now the begin queue is larger, so the end side expands cog and reaches dog and log (distance 2). Then the begin side expands dot, whose pattern do* contains dog, which the end side has reached. The result is 3 + 2 = 5.
The solution in Python
class Solution:
def processLevel(self, graph, queue, minDist, otherMinDist):
for _ in range(len(queue)):
word = queue.popleft()
for i in range(len(word)):
starWord = self.getStarWord(word, i)
for nextWord in graph.get(starWord, []):
if nextWord in otherMinDist:
return minDist[word] + otherMinDist[nextWord]
if nextWord not in minDist:
minDist[nextWord] = minDist[word] + 1
queue.append(nextWord)
return 0
def getStarWord(self, word, i):
return word[:i] + "*" + word[i + 1:]
def buildGraph(self, words):
graph = {}
for word in words:
for i in range(len(word)):
starWord = self.getStarWord(word, i)
graph[starWord] = graph.get(starWord, []) + [word]
return graph
def ladderLength(self, beginWord: str, endWord: str, words: List[str]) -> int:
if endWord not in words:
return 0
graph = self.buildGraph(words)
beginQueue, endQueue = deque(), deque()
beginMinDist, endMinDist = {}, {}
beginQueue.append(beginWord)
endQueue.append(endWord)
beginMinDist[beginWord], endMinDist[endWord] = 1, 1
result = 0
while beginQueue and endQueue:
if len(beginQueue) <= len(endQueue):
result = self.processLevel(graph, beginQueue, beginMinDist, endMinDist)
else:
result = self.processLevel(graph, endQueue, endMinDist, beginMinDist)
if result:
return result
return 0
Python details to notice:
- Slices build the pattern.
word[:i]is everything before indexi, andword[i + 1:]is everything after it. Strings are immutable, so a new string is created each time. For"hit"andi = 1the result is"h*t". dequefor the queue.popleft()removes the front inO(1), unlikelist.pop(0), which shifts every element. The class needsdequefromcollectionsto be available.- Dictionaries as visited sets. A word is visited if it is a key of
minDist, so one structure holds both the distance and the visited flag. graph.get(starWord, [])returns an empty list for an unknown pattern, so the inner loop simply runs zero times.- Passing containers shares them.
processLevelchanges the deque and the dictionaries it receives, and the caller sees those changes. Nothing is returned except the length. - List concatenation in
buildGraph.graph.get(starWord, []) + [word]creates a new list for every insertion.graph.setdefault(starWord, []).append(word)or adefaultdict(list)appends in place and is faster when a pattern has many words. - A nonzero result is truthy. A real sequence has at least two words, so
0can only mean no meeting.
Complexity
Let N be the number of words and L their length.
Time. Building the graph creates N * L patterns, and each slice costs O(L), so it takes O(N * L²). The search expands each visited word once per side, with L patterns per word and a bucket of neighbours per pattern. When the buckets are small it is about O(N * L²) again. In the worst case, such as many words sharing the same patterns, scanning the buckets can reach O(N² * L). Searching from both ends usually visits far fewer words than a single search.
Space: O(N * L²). The dictionary holds up to N * L patterns of length L, and the queues and distance dictionaries hold at most N + 2 words.
Edge cases and common mistakes
endWordis missing. The method returns 0 immediately.beginWordis not in the list. That is allowed. Only the begin side starts from it, which is why the begin side must expand first on a tie.- No connection. When one queue empties, the loop ends and the method returns 0.
- Adjacent words.
"hot"to"dot"with["dot"]returns 2, because the sequence contains two words. - Counting steps instead of words. The answer counts words, so a path with 4 changes has length 5. This is why each distance starts at 1.
- Stopping at the first meeting inside a level. This is safe only because whole levels are expanded. A meeting in an earlier call would have been found first.
- Using a list as a queue.
pop(0)works but costsO(n)each time.
Testing
"hit"to"cog"with["hot", "dot", "dog", "lot", "log", "cog"]returns5."hit"to"cog"with["hot", "dot", "dog", "lot", "log"]returns0."hot"to"dot"with["dot"]returns2.
