Problem overview
The method ladderLength receives beginWord, endWord and a list words. Each move changes one letter and must land on a word from the list. It returns the number of words in the shortest sequence from beginWord to endWord, counting both ends, or 0 when there is none. All words have the same length and are lowercase.
For "hit", "cog" and ["hot","dot","dog","lot","log","cog"] the shortest sequence is hit, hot, dot, dog, cog, so the answer is 5. Without "cog" in the list the answer is 0.
Approach: search from both ends and meet in the middle
A normal breadth-first search (BFS) from beginWord explores outward in all directions until it hits endWord. The number of words at each distance usually grows quickly, so the last levels are the expensive ones. Running a second BFS from endWord at the same time, and stopping when the two searches reach a common word, means each side only has to go about half the distance. Two small searches are cheaper than one large one.
The neighbors come from the pattern graph of the previous lesson: words that become the same string after one letter is replaced with * are neighbors. The graph is undirected, so the same graph serves both searches.
Each side keeps its own queue and its own minDist, which maps a word to the length of the shortest sequence from that side's start to the word, with both ends counted. A word has an entry exactly when that side has visited it. When one side steps onto a word the other side has already visited, the searches have met, and the two distances add up to the answer.
The searches expand one whole level at a time, and the side with fewer words in its queue goes first, since it is cheaper to grow.
Step by step
- Return 0 early if
wordsdoesn't containendWord: nothing can end there, and the second search starts from it. - Write
buildGraph, which takes the words and returns a[String: [String]]from pattern to matching words. For each word and each position it asksgetStarWordfor the pattern and appends the word to that pattern's list. - Write
getStarWord. It copies the word into a character array, sets positionito"*"and builds a string back from the array. - Set up both sides. In
ladderLength, build the graph, then createbeginQueueandendQueuewith their starting words andbeginMinDistandendMinDistwith the start words at distance 1. - Declare
resultas a variable initialized to 0 to hold what each level expansion returns. - Loop while neither queue is empty. If one side runs out of words, the searches can't meet.
- Write
processLevel, which expands one level of one side. It takes the graph, that side's queue and distances, and the other side's distances. The queue and distances areinout, because the function must change the caller's copies. - Take exactly the current level. Loop
queue.counttimes, removing the front word each time. The range is computed once, so words appended during this call wait for the next call. - Check each neighbor. For each position, look at the words in the pattern's bucket. If the other side has a distance for
nextWord, the searches have met: return this side's distance towordplus that distance. - Otherwise extend this side. If
nextWordis new to this side, give itminDist[word]! + 1and append it to the queue. - Return 0 if the level ended without a meeting. A real answer is at least 2, so 0 can't be confused with one.
- Choose a side. In the loop, expand the begin side when
beginQueue.count <= endQueue.count, and the end side otherwise. Ifresultis positive, return it. - Return 0 after the loop.
The solution in Swift
class Solution {
func getStarWord(_ word: String, _ i: Int) -> String {
var chars = Array(word)
chars[i] = "*"
return String(chars)
}
func buildGraph(_ words: [String]) -> [String: [String]] {
var graph = [String: [String]]()
for word in words {
let n = word.count
for i in 0..<n {
let starWord = getStarWord(word, i)
graph[starWord, default: []].append(word)
}
}
return graph
}
func processLevel(_ graph: [String: [String]], _ queue: inout [String], _ minDist: inout [String: Int], _ otherMinDist: [String: Int]) -> Int {
for _ in 0..<queue.count {
let word = queue.removeFirst()
let n = word.count
for i in 0..<n {
let starWord = getStarWord(word, i)
for nextWord in graph[starWord, default: []] {
if let other = otherMinDist[nextWord] {
return minDist[word]! + other
}
if minDist[nextWord] == nil {
minDist[nextWord] = minDist[word]! + 1
queue.append(nextWord)
}
}
}
}
return 0
}
func ladderLength(_ beginWord: String, _ endWord: String, _ words: [String]) -> Int {
if !words.contains(endWord) {
return 0
}
let graph = buildGraph(words)
var beginQueue = [String]()
var endQueue = [String]()
var beginMinDist = [String: Int]()
var endMinDist = [String: Int]()
beginQueue.append(beginWord)
endQueue.append(endWord)
beginMinDist[beginWord] = 1
endMinDist[endWord] = 1
var result = 0
while !beginQueue.isEmpty && !endQueue.isEmpty {
if beginQueue.count <= endQueue.count {
result = processLevel(graph, &beginQueue, &beginMinDist, endMinDist)
} else {
result = processLevel(graph, &endQueue, &endMinDist, beginMinDist)
}
if result > 0 {
return result
}
}
return 0
}
}
The Swift details worth knowing:
inoutparameters. Arrays and dictionaries are value types, so a plain parameter is a read-only copy. MarkingqueueandminDistasinoutletsprocessLevelchange the caller's variables, and the call site must write&beginQueueto show it.graphandotherMinDistare only read, so they are passed normally, and Swift avoids copying them unless they are changed.if let.if let other = otherMinDist[nextWord]runs its body only when the lookup is notnil, with the unwrapped distance bound toother.- Distance arithmetic. Each distance counts its own start word.
wordandnextWordare different words, sominDist[word]! + othercounts every word of the whole sequence exactly once. for _ in 0..<queue.count. The underscore discards the loop value. The range is built once from the queue's size at that moment, even though the loop body removes and appends elements.- Arrays as queues.
removeFirst()shifts the rest of the array, so a dequeue costs time proportional to the queue length.
Complexity
Let N be the number of words and L their length.
Time: O(N · L²) in the worst case. Building the graph takes O(N · L²), because each of the N · L patterns costs O(L) to create. Each side visits every word at most once, and a visit builds L patterns and scans buckets of at most 26 words. So the worst case matches the one-sided search. The gain is practical: on graphs where the number of words per level grows quickly, each side stops near the middle and visits far fewer words.
Space: O(N · L²). The graph stores up to N · L pattern strings of length L. The queues and distance tables add O(N · L).
Edge cases and common mistakes
- Start word not in the list. This is the reason for the
<=. With"hot","dot"and["dot"], both queues hold one word at the start. Using<would send the end side first. It would find nothing, since"hot"is not in the graph, would run out of words, and the method would return 0. With<=the begin side goes first and the answer is 2. - Target missing. The early check returns 0 before any graph is built.
- Expanding one word at a time instead of whole levels. The searches could meet through a longer sequence while a shorter one is still waiting in a queue.
- Forgetting
inoutor&. A parameter withoutinoutis a constant, so changingqueueorminDistinside the function is a compile error. Passing aninoutargument without&is an error too. - Adding 1 twice. The returned total is two distances added together. Adding another 1 would double-count the meeting point.
Testing
"hit","cog",["hot","dot","dog","lot","log","cog"]gives5."hit","cog",["hot","dot","dog","lot","log"]gives0."hot","dot",["dot"]gives2."hit","hot",["hot"]gives2.
