Problem overview
The method ladderLength receives a beginWord, an endWord and an Array[String] called words. It changes one letter at a time, and every word along the way must be in words. It returns the number of words in the shortest such sequence, counting both ends, or 0 when no sequence exists. All words have the same length and contain lowercase letters only.
For "hit" to "cog" with ["hot","dot","dog","lot","log","cog"], the sequence hit, hot, dot, dog, cog has 5 words, so the answer is 5. When "cog" is missing from the list, nothing can end there and the answer is 0. Note that the answer counts words, not changes: four changes make a sequence of five words.
Approach: a graph of words
Treat every word as a vertex, and join two words with an edge when they differ in exactly one position. The task is then the shortest path between two vertices in an unweighted graph, and the standard tool for that is breadth-first search (BFS). BFS visits the vertices in order of distance from the start: first the start, then everything one change away, then everything two changes away, and so on. The first time it reaches a vertex, it has found a shortest route to it.
This lesson builds the edges on the fly. For each word taken from the queue, it scans the whole list and tests every candidate with a helper that counts the positions where two strings differ. That is simple to write, and it is the slowest of the approaches to this problem. Later lessons replace the scan with faster neighbor lookups.
A map from word to distance does two jobs. Its values are the answers, and its keys are the set of words already reached. A word is given its distance when it is put into the queue, not when it is taken out. That way a word cannot be queued twice.
Step by step
- Create the queue as an empty
scala.collection.mutable.Queue[String]. - Create
minDist, a mutableHashMap[String, Int]from a word to the length of the shortest sequence that reaches it frombeginWord. - Start the search. Enqueue
beginWordand setminDist(beginWord)to 1, because a sequence holding only the first word has length 1. Maps are written to with parentheses:minDist(key) = value. - Wrap the loop in
breakable. Scala has nobreakkeyword. Thebreakthat this lesson uses comes fromscala.util.control.Breaksand works by throwing an exception that the enclosingbreakableblock catches. The loop itself iswhile (queue.nonEmpty). - Dequeue the front word into
word. - Stop at the target. If
wordequalsendWord, callbreak. BFS removes words in order of distance, so the distance stored forendWordis already the shortest. - Try every candidate. A
forloop runsnextWordoverwords. - Skip non-neighbors. Scala has no
continue, so the loop body gets its own innerbreakableblock, andbreakin it skips only the current candidate. The helpernumOfChangesreturns the number of differing positions. Anything other than exactly 1 is skipped: 0 means the same word, and 2 or more is too far. - Skip words already reached with
minDist.contains(nextWord). They were found by a sequence at least as short. - Record and enqueue. Otherwise
minDist(nextWord)becomesminDist(word) + 1, andnextWordjoins the queue. - Return the answer with
minDist.getOrElse(endWord, 0): the stored distance, or 0 ifendWordwas never reached. - Write
numOfChanges: avar differencesstarts at 0, a loop over0 until first.lengthadds 1 wheneverfirst(i) != second(i), anddifferencesis the last expression.
The solution in Scala
class Solution {
def numOfChanges(first: String, second: String): Int = {
var differences = 0
for (i <- 0 until first.length) {
if (first(i) != second(i)) {
differences += 1
}
}
differences
}
def ladderLength(beginWord: String, endWord: String, words: Array[String]): Int = {
val queue = scala.collection.mutable.Queue[String]()
val minDist = scala.collection.mutable.HashMap[String, Int]()
queue.enqueue(beginWord)
minDist(beginWord) = 1
breakable {
while (queue.nonEmpty) {
val word = queue.dequeue()
if (endWord == word) {
break
}
for (nextWord <- words) {
breakable {
if (numOfChanges(word, nextWord) != 1) {
break
}
if (minDist.contains(nextWord)) {
break
}
minDist(nextWord) = minDist(word) + 1
queue.enqueue(nextWord)
}
}
}
}
minDist.getOrElse(endWord, 0)
}
}
This code uses breakable and break, so the file needs import scala.util.control.Breaks._. The Scala details worth a closer look:
- Nested
breakableblocks.breakleaves the innermost enclosingbreakable. In the inner block it works likecontinue. In the outer block,breakends the BFS. Because the innerbreakablesits inside thefor, each candidate gets a fresh one. - Strings and characters. A string is indexed with parentheses,
first(i), and gives aChar. Comparing two characters with!=compares values. - No
++. Scala has no increment operator, so the counter usesdifferences += 1. - Map access.
minDist(word)throwsNoSuchElementExceptionfor a missing key, which is safe here becausewordalways came out of the queue after being given a distance.getOrElseis used for the final lookup because the key may be absent. - Last expression.
differencesand thegetOrElsecall have noreturnin front of them. The last expression of a block is its value.
Complexity
Let N be the number of words and L their length.
Time: O(N² * L). Each word enters the queue at most once. For every word taken out, the loop tests all N candidates, and each test compares up to L letters.
Space: O(N * L). The queue and the map hold at most one entry per word, and each entry is a string of length L.
Edge cases and common mistakes
endWordnot in the list. It can never be queued, so the method returns 0.beginWordnot in the list. That is allowed. The search starts from it whether or notwordsholds it. For"hit"to"hot"with["hot"], the answer is 2.- Counting changes instead of words. Starting
minDist(beginWord)at 0 would return 4 for the main example instead of 5. - Treating 0 differences as a neighbor. A word compared with itself differs in 0 places. The test must be "exactly 1", not "at most 1".
- Setting the distance on dequeue. The same word can then be queued many times before its first removal, which wastes work.
- Breaking in the wrong block. A
breakplaced directly in thefor, outside the innerbreakable, ends the whole BFS instead of skipping one candidate.
Testing
"hit","cog",["hot","dot","dog","lot","log","cog"]gives5."hit","cog",["hot","dot","dog","lot","log"]gives0."hot","dot",["dot"]gives2."a","c",["a","b","c"]gives2.
