Start learning free

LESSON 343 OF 348 · GRAPHS

Word Ladder in Kotlin: BFS Generating Neighbours with a HashSet

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

Given two words (beginWord and endWord), and a dictionary's word list, 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",
wordList = ["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"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

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

STEP 1 OF 16

Guided

Ctrl + Enter to check

KOTLIN · GRAPHS

Word Ladder in Kotlin, explained

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 exactly one letter and every word after the first is in the list. If there is no such chain, it returns 0.

For beginWord = "hit", endWord = "cog" and ["hot","dot","dog","lot","log","cog"], one shortest chain is hit -> hot -> dot -> dog -> cog. It holds 5 words, so the answer is 5. If "cog" is missing from the list, the answer is 0.

Approach: build the neighbours instead of searching for them

Treat each word as a node of a graph, with an edge between words that differ in one letter. A breadth-first search (BFS) from beginWord finds the shortest chain, because it visits all words one step away, then all words two steps away, and so on.

The simplest BFS finds the neighbours of a word by scanning the entire list and comparing letters. That costs O(N · L) per word. This lesson turns the question around. A word of length L has only L × 26 possible one-letter variants. Generate each variant and ask a HashSet whether it is in the list. A set lookup takes constant time on average, apart from hashing the string itself, which costs O(L).

That is the better trade whenever the list is long and the words are short. For words of length 3 there are at most 78 variants per word, no matter how many words the list holds. When the words are long and the list is short, scanning the list can be cheaper, so the two ideas are not strictly ranked. The next lessons on this problem improve the neighbour search again.

Step by step

Build wordSet from words with HashSet(words), so "is this candidate in the list?" is a lookup instead of a scan.
Create the queue, an empty ArrayDeque<String> named queue.
Create minDist, a HashMap<String, Int> mapping a word to the length of the shortest chain that reaches it. Its keys also act as the visited set.
Seed the search by adding beginWord to the queue and storing 1 for it: a chain with only one word has length 1, because the answer counts words, not changes.
Loop while the queue is not empty, taking the front into word.
Break at the target. If endWord == word, its shortest distance is already stored, because BFS takes words out in order of distance.
Loop over every position i of word and, inside it, over every letter c from 'a' to 'z'.
Build the candidate nextWord from the part before i, the letter c and the part after i. A string can't be modified in place, so a new one is made.
Filter. Skip the candidate if wordSet does not contain it, and skip it if minDist already has it. The second check also removes word itself, which appears whenever c equals the letter already at position i.
Record and enqueue. Store minDist[word]!! + 1 for nextWord and add it to the queue.
Return the distance stored for endWord, or 0 if minDist never got an entry for it.

The solution in Kotlin

class Solution {
    fun ladderLength(beginWord: String, endWord: String, words: List<String>): Int {
        val wordSet = HashSet(words)
        val queue = ArrayDeque<String>()
        val minDist = HashMap<String, Int>()
        queue.add(beginWord)
        minDist[beginWord] = 1
        while (queue.isNotEmpty()) {
            val word = queue.removeFirst()
            if (endWord == word) {
                break
            }
            for (i in word.indices) {
                for (c in 'a'..'z') {
                    val nextWord = word.substring(0, i) + c + word.substring(i + 1)
                    if (!wordSet.contains(nextWord)) {
                        continue
                    }
                    if (minDist.containsKey(nextWord)) {
                        continue
                    }
                    minDist[nextWord] = minDist[word]!! + 1
                    queue.add(nextWord)
                }
            }
        }
        return minDist.getOrDefault(endWord, 0)
    }
}

The Kotlin details worth a closer look:

Type inference on HashSet(words). The constructor copies the elements of a collection, and Kotlin infers HashSet<String> from the List<String> argument, so no type needs to be written.
Char ranges. 'a'..'z' is an inclusive range of characters, 26 of them, and a for loop can walk it like an Int range.
Building a string with +. word.substring(0, i) + c + word.substring(i + 1) appends a Char to a String, which gives a String. substring(start, end) excludes end, and substring(start) runs to the end of the string. For the last position, word.substring(i + 1) with i + 1 == word.length is the empty string, not an error.
Nullable map reads. minDist[word] has the type Int?. The !! is safe because every queued word has an entry. getOrDefault(endWord, 0) at the end supplies 0 for a word that was never reached.
continue targets the inner loop. Inside the for (c ...) loop, continue moves on to the next letter. break sits directly in the while loop, so it leaves the search.
Read-only List parameter. The function never changes words. The set is a separate copy.

Complexity

Let N be the number of words, L their length and Σ the alphabet size, 26 here.

Time: O(N · L² · Σ). Every word enters the queue at most once. For each one, the loops build L × Σ candidates, and building and hashing a candidate costs O(L). Copying the list into the set costs O(N · L), which is smaller.

Space: O(N · L). The set, the map and the queue each hold at most about N words of length L.

Edge cases and common mistakes

endWord missing from the list. It can never be generated as a candidate, so it never gets an entry and the function returns 0.
beginWord missing from the list. That is fine. It is queued directly, and only later words need to be in wordSet. For "hot", "dot" and ["dot"] the answer is 2.
Forgetting the wordSet check. The loops produce strings like "aot" that are not words in the list. Without the filter, the search would walk through them and report chains that use invalid words.
Visiting word itself. When c equals the current letter, the candidate is word. The minDist check discards it, because word has an entry already.
Distance 0 for the start. The answer counts words, so the first distance is 1. Starting at 0 makes every answer one too small.
Assuming lowercase. The letter loop covers 'a' to 'z' only. It would miss neighbours that differ by an uppercase letter or a digit, so the approach relies on the guarantee that all words are lowercase.

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.
"a", "c", ["a","b","c"] gives 2.
"hot", "dog", ["hot","dog"] gives 0.

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

Start learning free