Start learning free

LESSON 368 OF 414 · GRAPHS

Word Ladder in Scala: BFS with Wildcard Pattern Buckets

Practice O(N * L²) Read the full explanation

Given two words (beginWord and endWord), and a list of words (words), find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
words = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
words = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in words, therefore no possible transformation.

STEP 1 OF 21

Guided

Ctrl + Enter to check

SCALA · GRAPHS

Word Ladder in Scala, explained

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 its number of words, 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.

Approach: bucket words by pattern

A breadth-first search over words needs, for a given word, the list of words that differ from it in exactly one letter. Comparing it against every other word is slow, and trying all 26 letters at every position builds many candidates that do not exist. This lesson precomputes the neighbors instead.

Replace one position of a word with * to get a pattern. The word hot has three patterns: *ot, h*t and ho*. Two words differ in exactly one letter when they share a pattern, because they agree everywhere except where the star is. So the plan is to build a map from each pattern to the words that match it. After that, the neighbors of a word are the words in the buckets of its L patterns.

The BFS itself is the usual one. A map from word to distance doubles as the visited set, and a word gets its distance when it is queued.

Step by step

Create graph, a mutable.HashMap[String, mutable.ArrayBuffer[String]] from a pattern to the words that match it.
Loop over words, naming each one word.
Loop over each position i of word.
Write getStarWord(word, i). It is a method above ladderLength that takes a String and an Int and returns a String.
Build the pattern as the text before index i, then "*", then the text after it. This is the method's last line, so it is the value returned.
Call it in the two loops to get starWord.
Add the word to its bucket. graph.getOrElseUpdate(starWord, mutable.ArrayBuffer[String]()) returns the bucket, creating an empty one first when the key is missing. += word appends to it.
Create the queue as a mutable.Queue[String].
Create minDist, a mutable.HashMap[String, Int] from a word to the length of the shortest sequence that reaches it, counting both ends.
Enqueue beginWord.
Set minDist(beginWord) to 1. The answer counts words, not changes.
Set up the loop. A var done = false flag replaces break: the loop runs while queue.nonEmpty && !done.
Dequeue the front word into word.
Stop at the target. If endWord == word, set done to true. The neighbor work goes in an else, since setting a flag does not skip the rest of the iteration.
Loop over the positions of word and compute starWord for each. Everything in that bucket differs from word only at position i.
Loop over the bucket, using graph.getOrElse(starWord, mutable.ArrayBuffer[String]()). A pattern with no bucket gives an empty loop. That happens when beginWord is not in the list and one of its patterns matches nothing.
Skip visited words. if (!minDist.contains(nextWord)) ensures each word is visited once. word is in its own buckets, but it already has a distance, so it is skipped.
Record and enqueue: minDist(nextWord) = minDist(word) + 1, then queue.enqueue(nextWord).
Return minDist.getOrElse(endWord, 0).

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 ladderLength(beginWord: String, endWord: String, words: Array[String]): Int = {
        val graph = mutable.HashMap[String, mutable.ArrayBuffer[String]]()
        for (word <- words) {
            for (i <- 0 until word.length) {
                val starWord = getStarWord(word, i)
                graph.getOrElseUpdate(starWord, mutable.ArrayBuffer[String]()) += word
            }
        }
        val queue = mutable.Queue[String]()
        val minDist = mutable.HashMap[String, Int]()
        queue.enqueue(beginWord)
        minDist(beginWord) = 1
        var done = false
        while (queue.nonEmpty && !done) {
            val word = queue.dequeue()
            if (endWord == word) {
                done = true
            } else {
                for (i <- 0 until word.length) {
                    val starWord = getStarWord(word, i)
                    for (nextWord <- graph.getOrElse(starWord, mutable.ArrayBuffer[String]())) {
                        if (!minDist.contains(nextWord)) {
                            minDist(nextWord) = minDist(word) + 1
                            queue.enqueue(nextWord)
                        }
                    }
                }
            }
        }
        minDist.getOrElse(endWord, 0)
    }
}

Scala details worth a closer look:

The import. import scala.collection.mutable brings the package name into scope, so the code writes mutable.HashMap and mutable.Queue. Without mutable., Scala's default collections are immutable.
getOrElseUpdate. Its second argument is evaluated only when the key is missing. The new empty buffer is stored, and the call returns the stored buffer, so appending with += works in a single line.
getOrElse with a default. graph.getOrElse(starWord, mutable.ArrayBuffer[String]()) returns the stored bucket, or the default when the key is absent. Like getOrElseUpdate, it builds the default only when needed, and it does not store it.
Two starWord values. The first loop and the BFS each declare a val starWord inside their own loop body, so the names do not clash.
Iterating while changing the map. The loop runs over a bucket of graph, and the body changes minDist and queue, never graph, so the iteration is safe.

Complexity

Let N be the number of words and L their length.

Time: O(N * L²). Building the map creates L patterns per word, and each pattern costs O(L) to build and hash. In the BFS, each word is dequeued once and looks at its L buckets. Because the words are distinct and share a pattern only by differing at one position, a bucket holds at most 26 words, so walking the buckets adds a constant factor.

Space: O(N * L²). There are up to N * L patterns, and each is a string of length L. The buckets add N * L entries that refer to words already in memory.

Edge cases and common mistakes

endWord not in the list. Its bucket entries do not exist, so it is never reached and the result is 0.
beginWord not in the list. It is not a key or a bucket member, but its patterns still match the buckets of its neighbors. "hit" to "hot" with ["hot"] gives 2.
Revisiting words. A word sits in several buckets and can be found through each of its patterns. The check against minDist stops it from being queued twice.
Counting changes. Starting the distance at 0 gives an answer that is one too small.
Wrong slice for the pattern. substring(0, i) + "*" + substring(i) keeps the replaced letter and makes the pattern one character too long. The second part must start at i + 1.

Testing

"hit", "cog", ["hot","dot","dog","lot","log","cog"] gives 5.
"hit", "cog", ["hot","dot","dog","lot","log"] gives 0.
"hot", "dot", ["dot"] gives 2.
"hit", "hat", ["hat","hit"] gives 2.

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free