Start learning free

LESSON 431 OF 540 · TRIES

Word Search II in Kotlin: Trie and Backtracking DFS

Practice O(R · C · 4L) Read the full explanation

Given a grid of letters board with R rows and C columns, and an array of strings words, return every word of words that can be traced on the board.

A word is traced by a path of cells: its first letter is in some cell, and each next letter is in a cell next to the previous one, horizontally or vertically (not diagonally). A cell can be used only once in the same word.

Return each word found once, in any order: the output lists the words in alphabetical order. If no word can be traced, the answer is empty.

 

Example 1:

Input: board = [
  ["o", "a", "a", "n"],
  ["e", "t", "a", "e"],
  ["i", "h", "k", "r"],
  ["i", "f", "l", "v"]
], words = ["oath", "pea", "eat", "rain"]
Output: ["eat", "oath"]
Explanation: "oath" starts at the top-left "o", goes right to "a", down to "t" and down again to "h".
"eat" starts at the "e" at the right end of the second row, then goes left to "a" and left again to "t".
The board has no "p", so "pea" can't be traced, and no "a" is next to the "r", so neither can "rain".

Example 2:

Input: board = [
  ["a", "b"],
  ["c", "d"]
], words = ["abdb", "ad"]
Output: []
Explanation: "abdb" would go a → b → d and then back to "b", but that cell is already used in this word.
"a" and "d" touch only at a corner, so "ad" can't be traced either.

Example 3:

Input: board = [
  ["s", "e", "e"],
  ["n", "e", "t"]
], words = ["see", "seen", "set", "net", "tee", "teen"]
Output: ["net", "see", "seen", "tee"]
Explanation: "see" can be traced in two ways (its last "e" is either to the right or below), but it is listed once.
"seen" goes s → e → e (the one below) → n, so the path of "see" is the start of the path of "seen".
"set" can't be traced: the only "e" next to "s" is not next to "t". Neither can "teen": in every path t → e → e, the second "e" is the top middle one, which is not next to "n".

 

Constraints:

  • 1 <= R, C <= 12
  • Every cell of board holds a lowercase English letter.
  • 1 <= words.length <= 3 * 104
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters, and all the words are different.

Note:

Searching the board once for every word repeats the same work for words that start the same way. Put the words in a trie instead, and search the board once: a depth-first search from each cell follows only the trie's paths. With words of at most L letters, each search goes at most L cells deep, so the time is O(R * C * 4L), plus the time to build the trie, whatever the number of words.

STEP 1 OF 25
    Ctrl + Enter to check

    KOTLIN · TRIES

    Word Search Ii in Kotlin, explained

    Problem overview

    You get a grid of lowercase letters, board, and an array of words. findWords returns every word that can be traced on the board. A word is traced by a path of cells: the first letter is in some cell, and each next letter is in a cell directly above, below, left or right of the previous one. A cell can be used only once within one word. Each word is reported once, and the order of the returned list doesn't matter.

    In Kotlin the signature is fun findWords(board: Array<CharArray>, words: Array<String>): List<String>. Each row of the board is a CharArray.

    Take the board oaan / etae / ihkr / iflv and the words oath, pea, eat, rain. "oath" runs from the top-left o right, then down twice. "eat" starts at the e at the end of the second row and goes left twice. There is no p on the board, and no a touches the r. The result is [oath, eat].

    Approach

    The obvious plan is to search the board once for each word with a depth-first search. That repeats work: the words "oath" and "oats" both start with "oat", yet each search would walk the same cells again. With thousands of words, the repetition is expensive.

    The better plan is to search for all words at the same time. Put the words in a trie, a tree where each node has one child per next letter and the path from the root spells a prefix. Then run a single depth-first search from each cell, and let the trie steer it. At each step the search asks: does the trie have a child for this cell's letter? If not, no word continues along this path, and the search stops at once. If so, it moves down the trie and the board together.

    Two more ideas finish the solution:

    • Store the word at its last node. A node that ends a word holds the word itself. When the search reaches it, the word can go straight into the answer.
    • Backtracking. To stop a path from reusing a cell, the search overwrites the cell with '#' before going deeper and writes the letter back when it leaves. The trie holds only letters, so '#' never matches.

    Step by step

    The trie node

    1. children. Inside TrieNode, a val children set to a new HashMap<Char, TrieNode>() maps each next letter to its child node.
    2. word. A var word: String? = null holds the word that ends at this node. Most nodes end no word, so the type is nullable.

    Building the trie

    1. In findWords, create val root = TrieNode(), the empty prefix.
    2. For each word, start var node at root and go through its letters. If the letter isn't in node.children, store a new TrieNode() for it. Then move down: node = node.children[c]!!.
    3. After the letters, node is the end of the word: set node.word = word.

    Starting the searches

    1. Create val found = mutableListOf<String>() to collect the answers.
    2. Loop over every row in 0 until board.size and every col in 0 until board[0].size, calling dfs(board, row, col, root, found). A word can start in any cell. Then return found.

    The search, dfs

    1. Leave the board. If the cell is outside the grid, return. The four calls below step to neighbors without checking them first, so this check handles the edges.
    2. Read the letter into val letter. It is needed again at the end.
    3. Prune. If letter !in node.children, no word continues along this path, so return. This also catches the '#' marker, which makes a cell that is already in use a dead end.
    4. Move down the trie: val child = node.children[letter]!!.
    5. Collect a word. If child.word isn't null, the path spells that word. Add it to found, then set child.word = null. Clearing it means a second path that spells the same word finds nothing to add, so each word appears once.
    6. Mark and explore. Set board[row][col] = '#', call dfs for the cells below, above, right and left, all with child as the node, then restore the cell with board[row][col] = letter.

    The solution in Kotlin

    class TrieNode {
    val children = HashMap<Char, TrieNode>()
    var word: String? = null
}

class Solution {
    fun findWords(board: Array<CharArray>, words: Array<String>): List<String> {
        val root = TrieNode()
        for (word in words) {
            var node = root
            for (c in word) {
                if (c !in node.children) {
                    node.children[c] = TrieNode()
                }
                node = node.children[c]!!
            }
            node.word = word
        }
        val found = mutableListOf<String>()
        for (row in 0 until board.size) {
            for (col in 0 until board[0].size) {
                dfs(board, row, col, root, found)
            }
        }
        return found
    }

    fun dfs(board: Array<CharArray>, row: Int, col: Int, node: TrieNode, found: MutableList<String>) {
        if (row < 0 || row >= board.size || col < 0 || col >= board[0].size) {
            return
        }
        val letter = board[row][col]
        if (letter !in node.children) {
            return
        }
        val child = node.children[letter]!!
        if (child.word != null) {
            found.add(child.word!!)
            child.word = null
        }
        board[row][col] = '#'
        dfs(board, row + 1, col, child, found)
        dfs(board, row - 1, col, child, found)
        dfs(board, row, col + 1, child, found)
        dfs(board, row, col - 1, child, found)
        board[row][col] = letter
    }
}

    Kotlin details worth knowing

    • !! after a map lookup. node.children[c] has the type TrieNode?, because a map gives null for a missing key. The code has just made sure the key exists, so !! is safe.
    • !in. c !in node.children is !node.children.containsKey(c) written as an operator: for a map, in tests the keys.
    • Why child.word!!. found holds String, but word is a String?. Kotlin won't smart-cast it after the != null check, because it is a mutable property. Writing found.add(child.word) gives: smart cast to 'String' is impossible, because 'word' is a mutable property that could be mutated concurrently. The !! fixes it, and it is safe here because of the check just above.
    • Characters. A Char is written in single quotes, a String in double quotes. for (c in word) goes over the Chars of a string. '#' is the marker character.
    • The board changes in place. Array<CharArray> is mutable and passed by reference, so dfs writes into the caller's board. Every '#' is replaced by its letter before the call returns, so the board is the same afterwards.
    • The result type. The function returns found, a MutableList<String>, as a List<String>. It lists the words in the order they were found, not in alphabetical order.

    Complexity

    Let R and C be the board's dimensions and L the length of the longest word, at most 10.

    • Building the trie: O(total number of letters in all words), one step per letter.
    • Searching: a search from one cell goes at most L cells deep, since the trie has no path longer than the longest word. From the first cell it can go in 4 directions and after that in at most 3, because it can't step back onto the cell it came from. That gives at most 4 · 3^(L-1) paths per starting cell, so the time is O(R · C · 4 · 3^(L-1)) at worst. In practice the trie cuts most paths after a letter or two. The number of words appears only in the trie-building part, not in the search.
    • Space: O(total letters) for the trie, and O(L) for the recursion.

    Edge cases and common mistakes

    • Reusing a cell. On the board ab / cd, the word "abdb" would return to b. The marker stops this, so the result is empty. "ad" fails too: the two letters touch only at a corner.
    • Forgetting to restore the cell. If board[row][col] = letter is missing, cells stay blocked for every later path, and words get missed.
    • A word found by several paths. "see" on see / net has two paths. Clearing child.word keeps it in the result once.
    • Words that are prefixes of others. "see" and "seen" share a path. The word is collected when the search passes its node, and the search keeps going to look for longer words.
    • A word longer than the available path. On the board aa, the word "aaa" can't be traced, because it would need three different cells. The result is empty.
    • One-cell boards. A board of a single letter with the word of that letter works: the search from that cell finds it.
    • Diagonal steps. Only four directions are allowed; there are four calls to dfs, none diagonal.

    Testing

    These results come from running the solution above. The boards are written as rows separated by slashes:

    BoardWordsReturned
    oaan/etae/ihkr/iflvoath, pea, eat, rain[oath, eat]
    ab/cdabdb, ad[]
    see/netsee, seen, set, net, tee, teen[see, seen, net, tee]
    aa[a]
    aaaaa[]
    abab, a, b, ba[a, ab, b, ba]
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free