Start learning free

LESSON 367 OF 414 · GRAPHS

Word Ladder in Scala: BFS Trying Every Letter Change

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 16

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, it must find the shortest sequence from beginWord to endWord. The result is the number of words in that sequence, counting both ends, or 0 if there is none. 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: generate neighbors instead of scanning for them

This is a shortest-path problem on an unweighted graph where the words are the vertices, so it calls for breadth-first search. A search that scans the whole list to find the neighbors of each word costs O(N) comparisons per word. This lesson flips the work around: from a word of length L, there are only L * 26 words that differ from it in one position. Build each of those candidates, and keep the ones that are in the word list.

A set makes that membership test fast. Converting the array with toSet turns "is this candidate a real word?" from a scan of the array into an average O(1) lookup (plus the cost of hashing the string).

As in any BFS, a map from word to distance doubles as the visited set. A word gets its distance at the moment it is queued, so it can never be queued twice. Words come out of the queue in non-decreasing order of distance, so the first time endWord comes out, its stored distance is the shortest.

Step by step

Make a set. val wordSet = words.toSet creates an immutable Set[String].
Create the queue, a scala.collection.mutable.Queue[String].
Create minDist, a mutable Map[String, Int]: the length of the shortest sequence from beginWord to each word reached so far, counting both ends.
Enqueue beginWord to start the search.
Set minDist(beginWord) to 1, since a sequence of one word has length 1. The answer counts words, not changes.
Use a flag instead of break. Declare var done = false and loop while queue.nonEmpty && !done.
Dequeue the front word into word.
Test for the target. If word equals endWord, set done to true. Setting a flag does not skip the rest of the iteration, so the neighbor search goes in an else branch.
Loop over every position i of word.
Loop over the letters 'a' to 'z'. Ranges work for Char as they do for Int, and to includes both ends.
Build the candidate. Strings are immutable, so nextWord is made of the part of word before i, the letter c, and the part after i.
Check the dictionary. Scala has no continue, so the remaining checks are nested inside if (wordSet.contains(nextWord)).
Check that it is new. Inside it, if (!minDist.contains(nextWord)). A word that already has a distance was reached by a sequence at least as short. This also covers the case where c is the letter already at position i, which rebuilds word itself.
Record the distance as minDist(word) + 1.
Enqueue nextWord so that its own neighbors get explored later.
Return minDist.getOrElse(endWord, 0).

The solution in Scala

class Solution {
    def ladderLength(beginWord: String, endWord: String, words: Array[String]): Int = {
        val wordSet = words.toSet
        val queue = scala.collection.mutable.Queue[String]()
        val minDist = scala.collection.mutable.Map[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) {
                    for (c <- 'a' to 'z') {
                        val nextWord = word.substring(0, i) + c + word.substring(i + 1)
                        if (wordSet.contains(nextWord)) {
                            if (!minDist.contains(nextWord)) {
                                minDist(nextWord) = minDist(word) + 1
                                queue.enqueue(nextWord)
                            }
                        }
                    }
                }
            }
        }
        minDist.getOrElse(endWord, 0)
    }
}

Scala details worth a closer look:

Adding a Char to a String. word.substring(0, i) + c + word.substring(i + 1) works because the left operand is a String, so + appends the character's text. Two Char values added to each other are different: 'a' + 'b' is the Int 195.
substring bounds. substring(0, i) excludes index i, and substring(i + 1) runs to the end of the string. Together they skip exactly the letter at i.
Array versus Set. words.contains(x) scans the array. wordSet.contains(x) hashes x and looks it up.
The flag. var done is a variable because it changes. The condition queue.nonEmpty && !done is checked before every iteration.
getOrElse. minDist(endWord) would throw NoSuchElementException for an unreached word. getOrElse(endWord, 0) returns the default instead.
Mutable map. minDist(nextWord) = minDist(word) + 1 calls the map's update method.

Complexity

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

Time: O(N * L²), with a factor of 26. Each word is queued at most once. For each one, the loops build 26 * L candidates, and building and hashing a candidate costs O(L). The scanning version takes O(N² * L), so this version is faster when the list is long and the words are short.

Space: O(N * L). The set, the queue and the map each hold at most one string of length L per word.

Edge cases and common mistakes

endWord not in the list. Candidates must be in wordSet, so endWord is never queued and the result is 0.
beginWord not in the list. This is fine. It is queued directly, and only its neighbors have to be in the set. "hit" to "hot" with ["hot"] gives 2.
beginWord in the list. It already has a distance, so it is not queued again.
Counting changes. Starting minDist(beginWord) at 0 returns one less than the required length.
Distance on dequeue. Recording the distance when a word is removed from the queue lets the same word be queued many times first.
Adding characters. If the left side of the expression were a Char, as in word(i) + c, Scala would add the numeric codes and produce an Int.

Testing

"hit", "cog", ["hot","dot","dog","lot","log","cog"] gives 5.
"hit", "cog", ["hot","dot","dog","lot","log"] gives 0.
"hit", "hot", ["hot"] gives 2.
"hit", "cog", ["hot","dog","cog"] gives 0, because hot and dog differ in two positions.

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

Start learning free