Start learning free

LESSON 344 OF 348 · GRAPHS

Word Ladder in Kotlin: BFS with Wildcard Pattern Buckets

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 21

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, changing one letter per step, where every word after the first must be in the list. If no chain exists, it returns 0.

With beginWord = "hit", endWord = "cog" and ["hot","dot","dog","lot","log","cog"], the chain hit -> hot -> dot -> dog -> cog has 5 words, so the answer is 5. With "cog" removed from the list the answer is 0.

Approach: group words under wildcard patterns

A breadth-first search (BFS) from beginWord finds the shortest chain, but it needs the neighbours of each word quickly. Comparing a word with the whole list is slow. Trying all 26 letters at every position is quicker but wasteful when most variants are not words.

This lesson uses a different trick. Replace one letter 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 position precisely when they share a pattern: "hot" and "dot" both have "*ot", and "hot" and "hit" both have "h*t".

So the lesson builds a map from each pattern to the list of words that match it, once, before the search starts. The neighbours of any word are then the lists under its own L patterns. No letter guessing and no list-wide scans are needed. The same trick also works for beginWord without adding it to the list, because its patterns are looked up in the map built from the list words.

Step by step

Create graph, a HashMap<String, MutableList<String>> from a pattern to the words that match it.
Loop over words with word as the variable, and inside it over every position i in word.indices.
Write getStarWord(word, i) above ladderLength. It returns the part of word before i, then "*", then the part after i.
Fill the map. In the loops, compute starWord and add word to the list stored under it. getOrPut returns that list and stores a fresh empty one first if the key is missing.
Set up the search. Create the queue (an empty ArrayDeque<String>) and minDist, a HashMap<String, Int> from a word to the length of its shortest chain. The keys of minDist double as the visited set.
Seed it. Add beginWord to the queue and store 1 for it, since the answer counts words rather than changes.
Loop while the queue is not empty, taking the front word into word.
Break at the target. If endWord == word, stop. BFS dequeues words in order of distance, so the stored distance is the shortest.
Visit the neighbours. For each position i, compute starWord again and loop over the words stored under it in graph, as nextWord. A pattern with no entry gives a loop that runs zero times.
Take unseen neighbours only. If minDist has no entry for nextWord, store minDist[word]!! + 1 and add it to the queue. word matches its own patterns too, but it already has an entry, so it is skipped.
Return the distance stored for endWord, or 0 if it never got one.

The solution in Kotlin

class Solution {
    fun getStarWord(word: String, i: Int): String {
        return word.substring(0, i) + "*" + word.substring(i + 1)
    }

    fun ladderLength(beginWord: String, endWord: String, words: List<String>): Int {
        val graph = HashMap<String, MutableList<String>>()
        for (word in words) {
            for (i in word.indices) {
                val starWord = getStarWord(word, i)
                graph.getOrPut(starWord) { ArrayList() }.add(word)
            }
        }
        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) {
                val starWord = getStarWord(word, i)
                for (nextWord in graph.getOrDefault(starWord, ArrayList())) {
                    if (!minDist.containsKey(nextWord)) {
                        minDist[nextWord] = minDist[word]!! + 1
                        queue.add(nextWord)
                    }
                }
            }
        }
        return minDist.getOrDefault(endWord, 0)
    }
}

The Kotlin details worth a closer look:

getOrPut. graph.getOrPut(key) { ArrayList() } returns the existing list for key, or runs the lambda, stores the new list and returns it. The lambda runs only when the key is missing, so one expression covers "create if absent, then add".
The value type is MutableList. A plain List has no add. The map declares MutableList<String>, and the ArrayList() in the lambda fits it.
getOrDefault with an empty list. For a pattern with no bucket, graph.getOrDefault(starWord, ArrayList()) gives an empty list and the inner loop does nothing. A plain graph[starWord] would give null, which a for loop can't iterate.
Variable scopes. The name starWord appears twice, once in the graph-building loop and once in the search loop. Each is a val inside its own loop body, so they don't clash. The same goes for word.
Strings are immutable. getStarWord builds a new string from two substring calls. At the last position, word.substring(i + 1) is an empty string.
Nullable reads. minDist[word] is an Int?, and !! is safe because every dequeued word has an entry.

Complexity

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

Building the graph: O(N · L²). There are N × L patterns to add, and each takes O(L) to build and hash.

The search. Each word is queued once. Dequeuing it builds L patterns at O(L) each, then walks the matching buckets. In typical inputs a bucket is small and the whole search costs about O(N · L²) too. In the worst case, many words share one pattern (for example, hundreds of words that differ only at the same position), and every word in that bucket walks the whole bucket, which is quadratic in the bucket size.

Space: O(N · L²). The map holds N × L patterns, each a string of length L, and the lists hold references to the words.

Edge cases and common mistakes

endWord not in the list. No bucket can lead to it, so it never gets an entry in minDist and the answer is 0.
beginWord not in the list. This works: the search starts from it directly and finds its neighbours through its patterns. For "hot", "dot" and ["dot"] the answer is 2.
Forgetting that a word matches its own pattern. Every bucket contains the word that produced it. Without the minDist check, word would be queued again as its own neighbour.
Setting the distance on dequeue. The distance has to be recorded when a word is queued. Otherwise two words in the same level could both queue a shared neighbour.
Starting the count at 0. The answer counts words, so the first distance is 1.
Using graph[starWord] directly. That gives List?, which the for loop rejects at compile time. Use getOrDefault or ?: emptyList().

Testing

getStarWord("hit", 1) gives "h*t".
"hit", "cog", ["hot","dot","dog","lot","log","cog"] gives 5.
"hit", "cog", ["hot","dot","dog","lot","log"] gives 0.
"hot", "dot", ["dot"] 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