Start learning free

LESSON 431 OF 540 · TRIES

Word Search II in Go: Trie and Backtracking on a Grid

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

    GO · TRIES

    Word Search Ii in Go, explained

    Problem overview

    The function findWords receives a grid of lowercase letters, board, as a [][]byte, and a slice of strings, words. It returns every word 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 directly above, below, left or right of the previous one. Diagonal neighbours don't count, and a cell can be used only once within the same word. Each word is returned once, and the order of the result is not important to the algorithm.

    In the first example, the board is

    o a a n
e t a e
i h k r
i f l v

    and words = ["oath", "pea", "eat", "rain"]. The words oath and eat can be traced, so the answer is ["eat", "oath"] once sorted. In the second example, the board is ["ab", "cd"] and words = ["abdb", "ad"]. The word abdb would need to use the b twice, and a and d touch only at a corner, so the answer is empty.

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

    The direct method runs a search on the board for each word. With up to 30,000 words, that repeats the same work for words that begin the same way: oath and oat would both walk o, a, t from scratch.

    A trie stores all the words in a tree where each edge is a letter, so words with a common beginning share a path. The plan is:

    1. Insert every word into a trie.
    2. Start a depth-first search from every cell of the board, walking the trie at the same time.
    3. Follow a neighbour only if the trie has an edge for its letter. A path that doesn't begin any word is abandoned at once.
    4. Whenever the walk reaches a node where a word ends, record that word.

    One search from a cell looks for all the words at once, because the trie's root contains all of them. Words are at most L = 10 letters long, so a search goes at most L cells deep. Each step has at most four directions, which gives the statement's bound of O(R * C * 4^L) for the search, plus the time to build the trie, whatever the number of words. In practice the trie prunes most paths long before they reach that depth.

    Two details make it correct. First, a cell must not be used twice in one path, so the search marks the cell it is on and restores it when it leaves, which is backtracking. Second, a word can often be traced along several paths, so a word is cleared from the trie once it is found; later paths that spell it find nothing to add.

    Step by step

    Building the trie.

    1. Give TrieNode a children field of type map[rune]*TrieNode. It maps the next letter to a pointer to the child node. The keys are runes because range over a string yields runes, and the values are pointers so every walk works on the shared nodes.
    2. Give it a word field of type string. On the node where a word ends it holds that word; the empty string means no word ends there. Every word has at least one letter, so "" is never a real word.
    3. Write NewTrieNode. It returns a pointer to a new TrieNode whose children is an empty map made with make(map[rune]*TrieNode). A map has to be made before anything can be stored in it.
    4. Create the root in findWords: root := NewTrieNode(). It stands for the empty prefix.
    5. Loop over the words with range, skipping the index with _.
    6. Start at the root for each word: node := root.
    7. Loop over the letters c of the word. Each letter moves one level down.
    8. Create a missing edge. If node.children[c] is nil, store NewTrieNode() there. Reading a key that is not in a Go map gives the zero value of the element type, here a nil pointer.
    9. Move down: node = node.children[c].
    10. Mark the end. After the letters, set node.word = word. Keeping the whole word on the node, rather than a flag, lets the search report it the moment a path reaches the node.

    Searching the board.

    1. Create the result slice found := []string{}.
    2. Loop over the rows with row from 0 while row < len(board).
    3. Loop over the columns with col up to len(board[0]). Every row has the same length, so the first row gives it.
    4. Call dfs with board, row, col, root and &found. The pointer to the slice lets the helper store a longer slice back after append.
    5. Return found after both loops.

    The helper dfs.

    1. Stop off the board. If row is below 0 or at least len(board), or col is below 0 or at least len(board[0]), return. The four calls at the end step to the neighbours without checking them, so this check handles the edges.
    2. Read the cell's letter into letter. The board holds bytes, so letter is a byte. It is needed again at the end to put it back.
    3. Stop if no word continues this way. If node.children[rune(letter)] is nil, return. This check keeps the search small: only paths that begin some word are followed.
    4. Move down the trie: child := node.children[rune(letter)]. The conversion rune(letter) turns the byte into the rune that the map uses as a key.
    5. Check for a word. If child.word != "", the path spells that word.
    6. Record it: *found = append(*found, child.word).
    7. Clear it: child.word = "", so another path to the same word adds nothing.
    8. Mark the cell as used by setting board[row][col] = '#'. No word contains #, so a call that comes back to this cell stops at the check on node.children.
    9. Search below and above with row + 1 and row - 1, passing child as the node, because the path now includes this cell.
    10. Search right and left with col + 1 and col - 1.
    11. Put the letter back: board[row][col] = letter. The cell is free again for other paths. This undo is what makes it backtracking.

    The solution in Go

    type TrieNode struct {
    children map[rune]*TrieNode
    word string
}

func NewTrieNode() *TrieNode {
    return &TrieNode{children: make(map[rune]*TrieNode)}
}

func findWords(board [][]byte, words []string) []string {
    root := NewTrieNode()
    for _, word := range words {
        node := root
        for _, c := range word {
            if node.children[c] == nil {
                node.children[c] = NewTrieNode()
            }
            node = node.children[c]
        }
        node.word = word
    }
    found := []string{}
    for row := 0; row < len(board); row++ {
        for col := 0; col < len(board[0]); col++ {
            dfs(board, row, col, root, &found)
        }
    }
    return found
}

func dfs(board [][]byte, row int, col int, node *TrieNode, found *[]string) {
    if row < 0 || row >= len(board) || col < 0 || col >= len(board[0]) {
        return
    }
    letter := board[row][col]
    if node.children[rune(letter)] == nil {
        return
    }
    child := node.children[rune(letter)]
    if child.word != "" {
        *found = append(*found, child.word)
        child.word = ""
    }
    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 Go details worth knowing:

    • Runes and bytes. for _, c := range word gives c as a rune (an int32), while board[row][col] is a byte (a uint8). The two are different types, and Go does not convert between them silently, so the map lookup in dfs needs rune(letter). For lowercase English letters the byte and rune values are the same number.
    • A missing map key is not an error. node.children[c] returns nil for a letter with no child, so the code can test == nil without the v, ok := form. It works because the values are pointers, whose zero value is nil. Reading a missing key does not insert it.
    • Why found is a pointer to a slice. A slice passed to a function is a copy of its header (pointer, length, capacity). append can return a header for a new array, and the caller would never see it. With *[]string, the helper stores the result in the caller's variable: *found = append(*found, ...).
    • The board is changed and restored. A [][]byte shares its rows with the caller, so writing '#' changes the caller's board while the search runs. Every '#' is replaced by the saved letter before the call returns, so the board looks untouched afterwards. The character literal '#' in single quotes is a rune constant that fits into a byte.
    • Empty result. found starts as []string{}, so when nothing is found the function returns an empty, non-nil slice.
    • The order of the result. Words come out in the order the search finds them, which is not alphabetical. For the first example, the function returns ["oath" "eat"]. Sort a copy with sort.Strings if you need an alphabetical list.
    • The trie is used up. Clearing child.word changes the trie, which the function builds for itself on every call, so nothing is lost.

    Complexity

    Let R and C be the board's dimensions, L the maximum word length and W the number of words.

    Time: O(W * L + R * C * 4^L). Building the trie costs one step per letter, at most W * L. Each search from a cell follows only paths that start some word, goes at most L cells deep, and branches into at most four directions, but it never goes back to the cell it came from, so the real branching is smaller. The bound does not depend on the number of words, except through the trie's size.

    Space: O(W * L). The trie has at most one node per letter of every word. The recursion depth is at most L, and the result holds at most W words.

    Edge cases and common mistakes

    • Reusing a cell. On the board ["ab", "cd"], the word abdb is not found. Without the '#' mark, the path would return to the b.
    • Diagonal neighbours. On the same board, ad is not found. Only the four straight directions are searched.
    • Not restoring the cell. If the letter is not put back, later searches see '#' in cells that should hold letters, and words go missing.
    • The same word on several paths. On the board ["see", "net"], the word see can be traced in two ways, but it is returned once because the first path clears it from the trie.
    • A word that is a prefix of another. With words = ["a", "ab", "abc"] on the board ["abc"], all three are returned. A word is recorded on the way down, and the search continues past it.
    • One cell, one letter. On the board ["a"], the word a is found, and a word like aa would not be.
    • Mixing up bytes and runes. Indexing the map with letter directly does not compile, because the key type is rune.
    • Searching once per word. It gives the same answers, but it repeats the work for shared beginnings and is much slower with many words.

    Testing

    Results are shown sorted.

    • Board ["oaan", "etae", "ihkr", "iflv"], words ["oath", "pea", "eat", "rain"] gives ["eat", "oath"].
    • Board ["ab", "cd"], words ["abdb", "ad"] gives [].
    • Board ["see", "net"], words ["see", "seen", "set", "net", "tee", "teen"] gives ["net", "see", "seen", "tee"].
    • Board ["a"], words ["a"] gives ["a"].
    • Board ["aa", "aa"], words ["aaaa", "aaaaa", "aaa"] gives ["aaa", "aaaa"]: four cells allow words up to four letters.
    • Board ["abc"], words ["a", "ab", "abc"] gives ["a", "ab", "abc"].
    • Board ["aba"], words ["aba", "abab"] gives ["aba"].
    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free