Problem overview
The function ladderLength receives a beginWord, an endWord and a list words. It returns the number of words in the shortest chain from beginWord to endWord, where each step changes one letter and every word after the first is in the list. If no chain exists, it returns 0.
For beginWord = "hit", endWord = "cog" and ["hot","dot","dog","lot","log","cog"], the chain hit -> hot -> dot -> dog -> cog has 5 words, so the answer is 5.
Approach: search from both ends
A plain breadth-first search (BFS) from beginWord spreads out like a growing circle. If every word has about b neighbours and the chain has d steps, the circle holds roughly b^d words by the time it reaches the target. Two searches that start at opposite ends and stop when they meet only need to grow to depth about d / 2 each, and 2 · b^(d/2) is far smaller than b^d when the graph branches a lot. That is the idea of bidirectional BFS.
The neighbour lookup is the one from the previous lesson: each word is grouped under its wildcard patterns ("hot" gives "*ot", "h*t" and "ho*"), and two words are neighbours when they share a pattern.
Two details make the bidirectional search correct:
- Expand whole levels. If each side advanced one word at a time, the searches could meet through a longer chain while a shorter one was still waiting in a queue. Expanding a complete level before checking again means a shorter chain would have produced a meeting in an earlier call.
- Expand the smaller side. Growing the side whose queue is shorter keeps both circles small.
Step by step
- Reject a missing target. If
wordsdoes not containendWord, return 0 at once. The end search starts atendWordand looks up its patterns in a map built from the list, so without this check it could find a chain that ends at a word the list doesn't have. - Build the pattern map.
getStarWord(word, i)replaces the letter atiwith*.buildGraph(words)loops over every word and position and adds the word to the list stored under its pattern, usinggetOrPut, then returns the map. - Create two queues and two distance maps:
beginQueueandendQueue, andbeginMinDistandendMinDist. Each map gives the length of the shortest chain from that side's start to every word it has reached, counting both ends, and its keys are that side's visited set. - Seed both sides. Add
beginWordtobeginQueueandendWordtoendQueuewithaddLast, and store 1 for each in its own map. - Declare
var result = 0to receive the outcome of each expansion. - Loop while both queues have words. When one side runs dry, its circle can't grow and the two searches can never meet.
- Write
processLevel. It takes the pattern map, the queue and distances of the side being expanded, and the other side's distances, which it only reads.repeat(queue.size)runs its block once for each word currently in the queue. The size is read once, so words added meanwhile wait for the next call. - Dequeue and look at the neighbours. For each
word, loop over its positions, computestarWordand loop over the words in that bucket. - Detect the meeting. If the other side's map contains
nextWord, returnminDist[word]!! + otherMinDist[nextWord]!!. The first term counts the words from this side's start toword. The second counts the words fromnextWordto the other end. They are different words, so the sum is the length of the whole chain. - Otherwise grow the side. If
minDisthas no entry fornextWord, storeminDist[word]!! + 1andaddLastit to the queue for the next level. - End the level. After the
repeatblock, return 0, meaning no meeting happened. - Choose a side in the main loop. If
beginQueue.size <= endQueue.size, expand the begin side; otherwise expand the end side with the roles swapped. Ifresultis positive, return it. - Return 0 after the loop: one side ran out before the two met.
The solution in Kotlin
class Solution {
fun getStarWord(word: String, i: Int): String {
return word.substring(0, i) + "*" + word.substring(i + 1)
}
fun buildGraph(words: List<String>): MutableMap<String, MutableList<String>> {
val graph = HashMap<String, MutableList<String>>()
for (word in words) {
for (i in word.indices) {
val starWord = getStarWord(word, i)
graph.getOrPut(starWord) { ArrayList() }.add(word)
}
}
return graph
}
fun processLevel(graph: Map<String, MutableList<String>>, queue: ArrayDeque<String>, minDist: MutableMap<String, Int>, otherMinDist: Map<String, Int>): Int {
repeat(queue.size) {
val word = queue.removeFirst()
for (i in word.indices) {
val starWord = getStarWord(word, i)
for (nextWord in graph.getOrDefault(starWord, ArrayList())) {
if (otherMinDist.containsKey(nextWord)) {
return minDist[word]!! + otherMinDist[nextWord]!!
}
if (!minDist.containsKey(nextWord)) {
minDist[nextWord] = minDist[word]!! + 1
queue.addLast(nextWord)
}
}
}
}
return 0
}
fun ladderLength(beginWord: String, endWord: String, words: List<String>): Int {
if (!words.contains(endWord)) {
return 0
}
val graph = buildGraph(words)
val beginQueue = ArrayDeque<String>()
val endQueue = ArrayDeque<String>()
val beginMinDist = HashMap<String, Int>()
val endMinDist = HashMap<String, Int>()
beginQueue.addLast(beginWord)
endQueue.addLast(endWord)
beginMinDist[beginWord] = 1
endMinDist[endWord] = 1
var result = 0
while (beginQueue.isNotEmpty() && endQueue.isNotEmpty()) {
if (beginQueue.size <= endQueue.size) {
result = processLevel(graph, beginQueue, beginMinDist, endMinDist)
} else {
result = processLevel(graph, endQueue, endMinDist, beginMinDist)
}
if (result > 0) {
return result
}
}
return 0
}
}
The Kotlin details worth a closer look:
returninsiderepeat.repeatis an inline function, so the block is not a separate function: areturnin it returns fromprocessLevelitself. That is what lets the meeting check exit with the answer from deep inside three loops.- Read-only versus mutable parameters.
minDistis aMutableMapbecauseprocessLevelwrites to it.otherMinDistandgraphare read-onlyMaptypes, which promises the function won't change them. AHashMapcan be passed for either. queue.sizeis read once.repeat(queue.size)evaluates its argument before the first run, so words added byaddLastinside the block do not extend the loop.- Nullable lookups. Reading a map gives
Int?. BothminDist[word]!!andotherMinDist[nextWord]!!are safe: the first word was queued with an entry, and the second was just found withcontainsKey. var resultand assignment in both branches. Theif/elseassigns the same variable, which is then tested after it.addLastandremoveFirstwork as the back and front of the queue.getOrPutandgetOrDefaultbehave as in the previous lesson.
Complexity
Let N be the number of words and L their length.
Time. Building the pattern map costs O(N · L²). In the worst case, the two searches together still touch every word once, with O(L²) work per word for the patterns, so the worst-case bound is the same as for a single BFS. The gain is in practice: on a graph with many neighbours per word, the two circles meet after exploring far fewer words than one circle would.
Space: O(N · L²). The pattern map holds N × L patterns of length L. The queues and distance maps hold at most N words each.
Edge cases and common mistakes
endWordnot in the list. The first line returns 0. For"hit","cog"and["hot","dot","dog","lot","log"]that is the correct answer.beginWordnot in the list. This is allowed, but it needs care. The end side can never step ontobeginWord, because the pattern map is built from the list only. Only the begin side's first expansion linksbeginWordto the other words. That is why a tie goes to the begin side, with<=. With<,"hot","dot"and["dot"]gives 0, because the end side expands first, finds nothing and runs out. With<=the answer is 2.- Expanding one word at a time. A meeting found mid-level may not be the shortest chain. Expanding whole levels avoids that.
- Adding the two distances wrongly. Each distance already counts its own start word, and the two words at the meeting are distinct, so the sum needs no
+ 1or- 1. For the first example it is 3 + 2 = 5. - Not stopping when a side is empty. If the loop ran while only one queue had words, it would call
processLevelon an empty queue and never end. - Confusing 0 with an answer. A real chain has at least two words, so a 0 from
processLevelcan only mean "no meeting yet".
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."hot","dog",["hot","dog"]gives0.