Start learning free

LESSON 342 OF 348 · GRAPHS

Word Ladder in Kotlin: BFS Over Words, O(N² · L)

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 of words, words. It returns the length of the shortest chain of words that starts at beginWord and ends at endWord, where each word in the chain differs from the previous one in exactly one letter and every word after the first must be in the list. The length counts words, not changes. If no chain exists, the function returns 0.

In the first example, beginWord = "hit", endWord = "cog" and the list is ["hot","dot","dog","lot","log","cog"]. One shortest chain is hit -> hot -> dot -> dog -> cog: five words, so the answer is 5. In the second example the list has no "cog", so the chain can never end and the answer is 0.

Approach: breadth-first search

Think of every word as a node and draw an edge between two words that differ in exactly one position. The question becomes: how many nodes are on the shortest path from beginWord to endWord? Shortest paths in a graph where every edge costs the same are exactly what breadth-first search (BFS) finds.

BFS keeps a queue. It starts with beginWord, then repeatedly takes the word at the front and adds every unseen neighbour to the back. Because the queue is first in, first out, all words one step away come out before any word two steps away, and so on. The first time endWord comes out of the queue, the distance recorded for it is the shortest one.

This lesson never builds the graph explicitly. For each word taken from the queue, it scans the whole list and tests every candidate. That test costs O(L) for words of length L, and the scan happens once per dequeued word, so the total is O(N² · L) for N words. It is the simplest version. The other lessons on this problem speed it up by generating the neighbours directly, by grouping words under wildcard patterns, and by searching from both ends.

Step by step

Create the queue as an empty ArrayDeque<String> named queue. It adds at the back and removes from the front.
Create minDist, a HashMap<String, Int> from a word to the length of the shortest chain that reaches it from beginWord. A word with an entry has been reached already, so the map doubles as the visited set.
Seed the search. Add beginWord to the queue and store 1 for it. A chain holding only the first word has length 1, because the answer counts words.
Loop while the queue is not empty. When it runs dry, every reachable word has been processed.
Take the front word into a val named word.
Stop at the target. If word equals endWord, break. Its distance is already in the map.
Try every candidate. Loop over words with nextWord as the variable.
Skip non-neighbours. A helper, numOfChanges(first, second), counts the positions where two strings differ. Anything other than exactly 1 is skipped: 0 is the same word and 2 or more is too far away.
Skip words already reached. If minDist has nextWord, an earlier and not longer chain reached it.
Record and enqueue. Otherwise store minDist[word]!! + 1 for nextWord and add it to the queue.
Return the result. After the loop, return the stored distance for endWord, or 0 if it has none.
Write numOfChanges. Start a counter differences at 0, loop over first.indices, add one whenever first[i] differs from second[i], and return the counter. All words have the same length, so one index works for both strings.

The solution in Kotlin

class Solution {
    fun numOfChanges(first: String, second: String): Int {
        var differences = 0
        for (i in first.indices) {
            if (first[i] != second[i]) {
                differences++
            }
        }
        return differences
    }

    fun ladderLength(beginWord: String, endWord: String, words: List<String>): Int {
        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 (nextWord in words) {
                if (numOfChanges(word, nextWord) != 1) {
                    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:

ArrayDeque is Kotlin's own. With no import, ArrayDeque is kotlin.collections.ArrayDeque. add appends at the back and removeFirst() takes from the front, both in amortized constant time. On an empty deque, removeFirst() throws NoSuchElementException, which is why the loop tests isNotEmpty() first.
Indexing a map gives a nullable value. minDist[word] has the type Int?, because a missing key gives null. The !! operator says "this is not null" and throws if it is. Here it is safe: every word in the queue was given an entry before it was queued.
getOrDefault replaces the null. minDist.getOrDefault(endWord, 0) returns 0 when endWord was never reached, so the function returns a plain Int.
== compares contents. endWord == word calls equals, so two different String objects with the same letters are equal. === would compare references.
first.indices is the range 0 until first.length. Indexing a string, first[i], gives a Char, and != compares two chars by value.
continue inside for jumps to the next nextWord. break leaves the while loop, since the nearest enclosing loop at that point is the while.

Complexity

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

Time: O(N² · L). Each word enters the queue at most once, because a word gets its entry in minDist at the moment it is queued. For each dequeued word the loop looks at all N list words, and numOfChanges costs O(L) each. That gives N dequeues times N candidates times L per comparison.

Space: O(N · L). The map and the queue hold at most N + 1 words of length L.

Edge cases and common mistakes

endWord not in the list. Example 2 returns 0. The search never queues "cog", so the map has no entry for it. Without getOrDefault, the lookup would give null.
beginWord not in the list. That is allowed. With beginWord = "hot", endWord = "dot" and words = ["dot"], the answer is 2. The search starts from beginWord whether or not it is listed.
Counting changes instead of words. Starting the first distance at 0 would make every answer one too small. A chain from "hit" to "hot" has 2 words and one change.
Accepting any small difference. Only an exact difference of 1 is a valid step. A difference of 0 means the same word, so a test like numOfChanges(...) > 1 would let a word count as its own neighbour.
Marking words as seen too late. Storing the distance when a word is dequeued, rather than when it is queued, lets the same word enter the queue several times before it is processed.
No path. beginWord = "hot", endWord = "dog" and words = ["hot", "dog"] give 0: the two words differ in two positions and nothing links them.

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