Start learning free

LESSON 432 OF 541 · TRIES

Word Search II in Swift: Trie and Backtracking

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 26
    Ctrl + Enter to check

    SWIFT · TRIES

    Word Search Ii in Swift, explained

    Problem overview

    findWords receives a grid of letters, board (an array of arrays of Character), and an array of strings, words. It returns every word that can be traced on the board. A word is traced through cells where each next letter sits right, left, above or below the previous one, and no cell is used twice within one word. Each word is reported once, in any order.

    In the first example the board is oaan / etae / ihkr / iflv and the words are oath, pea, eat and rain. oath starts at the top-left o, goes right, down and down. 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, so the result holds oath and eat.

    Approach: one search for all words, guided by a trie

    Searching the board separately for each word repeats work: words that begin with the same letters trace the same paths. A trie fixes that. It is a tree where each node stands for a prefix and has one child per possible next letter. Put all the words in a trie, then run one depth-first search from each cell, following only the trie's paths. A path that leaves the trie spells a prefix of no word, so the search stops there at once.

    The trie node in this lesson has two properties: children, a dictionary from Character to child node, and word, a String? that holds the whole word on the node where a word ends and is nil elsewhere. Keeping the word itself, rather than a flag, lets the search append it the moment its path is complete.

    The search marks the cell it is on as used, explores the four neighbours, and puts the letter back when it leaves. That undo is what makes it backtracking: another path can use the cell again.

    Step by step

    1. The trie node. TrieNode gets children, an empty [Character: TrieNode], and word, a String? that starts as nil.
    2. The root. In findWords, create a TrieNode for the empty prefix.
    3. Insert each word. For every word, start a var node at the root and walk through its letters. When node.children[c] is nil, store a new TrieNode there, then step into that child.
    4. Mark the end. After the last letter, set node.word to the word.
    5. Prepare the search. Create the empty list found, and a copy of the board named grid, since the search needs to mark cells and parameters are constants.
    6. Start from every cell. Two nested loops over row in 0..<grid.count and col in 0..<grid[0].count call dfs with &grid, the cell, the trie root and &found. Then return found.
    7. Off the board. In dfs, return when the row or column is outside the grid. Neighbour calls don't check their cells first, so this is where those stop.
    8. Read the letter of the cell into letter. It is needed again at the end.
    9. No such path. If node.children[letter] is nil, no word continues with this letter: return. This is the check that keeps the search small.
    10. Step into the trie. child is node.children[letter]!, the prefix so far plus this cell.
    11. A word ends here. When child.word isn't nil, append it to found and set it to nil. Clearing it means a second path to the same word adds nothing.
    12. Mark the cell by writing "#" into it. No word contains #, so any call that returns to this cell stops at the trie check.
    13. Explore the neighbours: four calls, for row + 1, row - 1, col + 1 and col - 1, all continuing from child.
    14. Restore the letter in the cell.

    The solution in Swift

    class TrieNode {
    var children: [Character: TrieNode] = [:]
    var word: String? = nil
}

class Solution {
    func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
        let root = TrieNode()
        for word in words {
            var node = root
            for c in word {
                if node.children[c] == nil {
                    node.children[c] = TrieNode()
                }
                node = node.children[c]!
            }
            node.word = word
        }
        var found = [String]()
        var grid = board
        for row in 0..<grid.count {
            for col in 0..<grid[0].count {
                dfs(&grid, row, col, root, &found)
            }
        }
        return found
    }

    func dfs(_ board: inout [[Character]], _ row: Int, _ col: Int, _ node: TrieNode, _ found: inout [String]) {
        if row < 0 || row >= board.count || col < 0 || col >= board[0].count {
            return
        }
        let letter = board[row][col]
        if node.children[letter] == nil {
            return
        }
        let child = node.children[letter]!
        if child.word != nil {
            found.append(child.word!)
            child.word = nil
        }
        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
    }
}

    The Swift details worth a closer look:

    • Classes for trie nodes. TrieNode is a class, so every variable that holds a node refers to the same object. That is why node.children[c] = TrieNode() changes the trie, and why child.word = nil inside dfs is seen by every later call. A struct would be copied on assignment and the changes would be lost.
    • inout parameters. Arrays are value types, so dfs would get its own copy of the board and the list. Declaring the parameters inout and passing &grid and &found lets the function change the caller's variables. The var grid = board line makes a copy because the parameter board of findWords is a constant.
    • Optional dictionary lookups. node.children[letter] is a TrieNode?: nil for a missing key. The code tests for nil first, and only then uses !, so it can't crash. The same goes for child.word! after the != nil test.
    • Character literals. "#" is a Character when it is assigned into a [[Character]]. The dictionary keys are Character too, because looping over a String gives characters.
    • Columns come from the first row. grid[0].count is the number of columns because every row has the same length.

    Complexity

    Time. Building the trie takes time proportional to the total number of letters in words. The search starts at R * C cells, and a path is at most L cells long, where L is the longest word, with at most four directions at each step. The cost is therefore at most O(R * C * 4^L), whatever the number of words, and usually much smaller because most paths leave the trie after a few letters.

    Space. The trie holds up to one node per letter of every word. The recursion goes at most L cells deep, and the grid copy adds R * C cells.

    Edge cases and common mistakes

    • Reusing a cell. On the board ab / cd, the word abdb would need the b twice, and ad would need a diagonal step. The result is empty.
    • The same word along several paths. On see / net, see can be traced two ways. Setting child.word to nil after the first find keeps it in the result once.
    • Words that share a path. see and seen both succeed on that board. The search appends see when it passes the node where it ends, and keeps going to reach seen.
    • Forgetting to restore the cell. Without the last line of dfs, cells stay marked after the search leaves them, and words that need them are missed.
    • A one-cell board. a with the word a finds it, and with aa finds nothing.
    • Result order. The words come back in the order the search finds them, not alphabetically: the first example returns oath and then eat. Sort the result if you need alphabetical order.
    • Long words on a small board. On a 3 by 4 board of as, the words aa, aaa and aaaaaaaaaa are all found, since the board has enough cells for a path of ten letters.

    Testing

    • Board oaan / etae / ihkr / iflv, words oath, pea, eat, rain gives ["oath", "eat"].
    • Board ab / cd, words abdb, ad gives [].
    • Board see / net, words see, seen, set, net, tee, teen gives ["see", "seen", "net", "tee"].
    • Board a, words a gives ["a"]; with words aa it gives [].
    • Board aaaa / aaaa / aaaa, words aaaaaaaaaa, aaa, aa gives all three words (["aa", "aaa", "aaaaaaaaaa"] once sorted).
    Keep going with Swift500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free