Problem overview
The method ladderLength receives a beginWord, an endWord and an Array[String] called words. Changing one letter at a time, with every word along the way in words, find the shortest sequence from beginWord to endWord. Return the number of words in it, counting both ends, or 0 if no sequence exists. All words have the same length and use lowercase letters only.
For "hit", "cog" and ["hot","dot","dog","lot","log","cog"], the shortest sequence is hit, hot, dot, dog, cog, so the answer is 5. If "cog" is not in the list, the answer is 0.
Approach: search from both ends
A breadth-first search from beginWord grows a wider and wider ring of words. If every word has about b neighbors and the answer is d words long, the ring reaches roughly b to the power d words before it touches endWord. Bidirectional search runs one BFS from each end. Each side only has to go about halfway, so the two rings stay much smaller than one big ring. The answer is found where they meet.
Finding neighbors still uses the pattern buckets: replace one position of a word with *, and words that share the resulting pattern differ in exactly that position. The map from pattern to words is built once, up front.
Two details make the meeting logic correct:
- Expand whole levels. Each turn processes every word currently in one side's queue, and the words it adds wait for the next turn. If the sides expanded a word at a time, they could meet through a long sequence while a shorter one was still waiting in a queue.
- Add the distances. Each side stores distances that count its own starting word. When a side reaches a word the other side has visited, the sequence length is the distance of the current word plus the other side's distance of the neighbor. No word is counted twice, because the current word and the neighbor are different words.
To keep the search cheap, each turn expands the side whose queue is smaller.
Step by step
- Reject a missing target early. If
wordsdoes not containendWord, return 0 right away. The second search starts fromendWord, and no sequence can end at a word outside the list. This is one of the places where an explicitreturnis needed, because the method must stop early. - Write
getStarWord(word, i), which builds the pattern with a*at indexiusing twosubstringcalls. - Write
buildGraph(words). It creates amutable.Map[String, mutable.ListBuffer[String]]calledgraph, loops over each word and each of its positions, and appends the word to the bucket of its pattern withgetOrElseUpdate. The last expression isgraph. - Call it from
ladderLengthto getgraph. - Create two queues and two distance maps.
beginQueueandendQueuehold the frontiers, andbeginMinDistandendMinDistrecord each side's distances. The keys of each map are also that side's visited set. - Seed both sides. Enqueue
beginWordandendWordinto their queues, and set each side's starting distance to 1. - Declare
var result = 0, which will hold what each expansion returns. - Loop while both queues are non-empty. Once one side has run out of words, the searches can never meet.
- Write
processLevel. It takes the graph, the queue to expand, that side's distances and the other side's distances, and returns anInt. Mutable collections are passed by reference, so the changes it makes are visible to the caller. - Take a snapshot of the level.
for (_ <- 0 until queue.size)builds its range once, before the loop runs. Words enqueued during the loop do not extend it, so exactly the current level is processed. The_is used because the counter is not needed. - Dequeue a word and walk its patterns. For each position, compute the pattern and loop over the bucket (an empty one if the pattern has no entry).
- Check for the meeting first. If
otherMinDist.contains(nextWord), returnminDist(word) + otherMinDist(nextWord). - Otherwise visit new words. If
minDistdoes not containnextWord, give itminDist(word) + 1and enqueue it for the next level. - End with 0. Returning 0 from
processLevelmeans this level did not meet the other search. A real sequence has at least two words, so 0 cannot be mistaken for an answer. - Choose a side. In the main loop, if
beginQueue.size <= endQueue.size, expand the begin side, passing its queue and distances first. Otherwise expand the end side with the roles swapped. The<=sends the first turn to the begin side, which matters whenbeginWordis not in the list: the end side can never step onto it, so only the begin side's expansion links it to the other words. - Return when they meet. If
resultis greater than 0, return it. After the loop, the last expression is0.
The solution in Scala
import scala.collection.mutable
class Solution {
def getStarWord(word: String, i: Int): String = {
word.substring(0, i) + "*" + word.substring(i + 1)
}
def buildGraph(words: Array[String]): mutable.Map[String, mutable.ListBuffer[String]] = {
val graph = mutable.Map[String, mutable.ListBuffer[String]]()
for (word <- words) {
for (i <- 0 until word.length) {
val starWord = getStarWord(word, i)
graph.getOrElseUpdate(starWord, mutable.ListBuffer[String]()) += word
}
}
graph
}
def processLevel(graph: mutable.Map[String, mutable.ListBuffer[String]], queue: mutable.Queue[String], minDist: mutable.Map[String, Int], otherMinDist: mutable.Map[String, Int]): Int = {
for (_ <- 0 until queue.size) {
val word = queue.dequeue()
for (i <- 0 until word.length) {
val starWord = getStarWord(word, i)
for (nextWord <- graph.getOrElse(starWord, mutable.ListBuffer[String]())) {
if (otherMinDist.contains(nextWord)) {
return minDist(word) + otherMinDist(nextWord)
}
if (!minDist.contains(nextWord)) {
minDist(nextWord) = minDist(word) + 1
queue.enqueue(nextWord)
}
}
}
}
0
}
def ladderLength(beginWord: String, endWord: String, words: Array[String]): Int = {
if (!words.contains(endWord)) {
return 0
}
val graph = buildGraph(words)
val beginQueue = mutable.Queue[String]()
val endQueue = mutable.Queue[String]()
val beginMinDist = mutable.Map[String, Int]()
val endMinDist = mutable.Map[String, Int]()
beginQueue.enqueue(beginWord)
endQueue.enqueue(endWord)
beginMinDist(beginWord) = 1
endMinDist(endWord) = 1
var result = 0
while (beginQueue.nonEmpty && endQueue.nonEmpty) {
if (beginQueue.size <= endQueue.size) {
result = processLevel(graph, beginQueue, beginMinDist, endMinDist)
} else {
result = processLevel(graph, endQueue, endMinDist, beginMinDist)
}
if (result > 0) {
return result
}
}
0
}
}
Scala details worth a closer look:
- Early
returnfrom inside loops. Scala methods normally return their last expression, but here the method has to stop in the middle of nested loops. Areturninside aforbody works, because the body is a function literal andreturnleaves the enclosing method. Scala 3.5 compiles the one inprocessLevelwith a warning that non-local returns are no longer supported, and the code runs and gives the right answers. - Aliasing. The same method serves both sides. For the end side, the call passes
endMinDistasminDistandbeginMinDistasotherMinDist. Because maps and queues are passed by reference,processLevelupdates the caller's collections. - The range snapshot.
0 until queue.sizeis evaluated once, so the count is fixed even though the queue grows and shrinks inside the loop. - Method order. Inside a class, a method can call another one defined above or below it, so the helpers can sit before
ladderLength. - Result types. The two branches of the
if/elseare statements that assign to avar, so the types are not combined into a result.
Complexity
Let N be the number of words and L their length.
Time: O(N * L²) in the worst case. Building the graph costs O(N * L²): L patterns per word, each built and hashed in O(L). Each side dequeues a word at most once, and a word looks at L buckets of at most 26 words each. The worst case is the same as a one-sided search that uses the same buckets. In practice, two small rings visit far fewer words than one large ring.
Space: O(N * L²). The patterns dominate: up to N * L strings of length L. The queues and distance maps hold at most one entry per word per side.
Edge cases and common mistakes
endWordnot in the list. The early return gives 0 before anything else is built.beginWordnot in the list. It is allowed. For"hot"to"dot"with["dot"]the answer is 2. With<in the side choice, the end side would go first, never findhotin the graph, run out of words and return 0.- Expanding a single word per turn. The sides can then meet through a longer sequence while a shorter one waits in a queue.
- Adding 1 too many. Since both distances count their starting word, the sum
minDist(word) + otherMinDist(nextWord)already is the number of words. Adding another 1 would overcount. - Using the result 0 as a valid answer. It means no meeting yet in
processLevel, and "no sequence" at the end ofladderLength. - Disconnected words. If one side runs out of words first, the loop ends and the method returns 0.
Testing
"hit","cog",["hot","dot","dog","lot","log","cog"]gives5."hit","cog",["hot","dot","dog","lot","log"]gives0."hot","dot",["dot"]gives2."hit","cog",["hit","hot","dot","dog","cog"]gives5."hit","cog",["hot","dog","cog"]gives0.
