Word Search II

You are given an m x n grid of lowercase letters, board, and a list of distinct strings, words. Return every word from the list that can be spelled on the board. A word is spelled by a path of cells that are next to each other horizontally or vertically, and one cell may appear at most once in the same word. The answer may be in any order. This is LeetCode 212.

Limits: 1 <= m, n <= 12, 1 <= words.length <= 3 * 10^4, and 1 <= words[i].length <= 10.

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: ["oath","eat"]
Example 2
Input: board = [["a","b"], ["c","d"]], words = ["abcb"]
Output: []

How to Think About It

Step 1: One word at a time is too slow

For a single word this is Word Search: start a depth-first search from every cell, mark cells on the current path, and undo the mark when you step back. Running that search once per word repeats the same work up to 3 脳 10^4 times. Words such as "oath" and "oat" share a prefix, yet each search walks that prefix again.

Step 2: Search for all words at once

Put every word into a trie, as in Implement Trie. Now one board search can follow the trie at the same time. Stepping onto a cell with letter ch means moving to the trie child for ch.

  • If that child does not exist, no word starts with the current path, so this branch stops at once.
  • If the child marks the end of a word, the path spells that word, so it is added to the answer.

Every path explored is a prefix of at least one word, and each prefix is shared by all the words that begin with it.

Step 3: Report a word once

The same word can often be traced along two different paths. Clearing the word from its trie node right after it is found makes later paths ignore it.

Step 4: Cut off finished branches

Once every word below a trie node has been found, that node only wastes time: the search would keep walking prefixes that cannot lead to anything new. So when the search returns from a node that has no children and no word left, it removes the node from its parent. Removals bubble up, so a whole finished branch disappears.

The effect can be large. On a 12 脳 12 board of the letter a, with the words "a", "aa", up to ten a's, the search with pruning enters 10 cells in total. Without the pruning it enters 1,883,664.

Walkthrough

Example 1. Cells are written as (row, column). The trie roots are o, p, e and r, so the search only goes past a starting cell holding one of those letters. These are all the cells the search entered, in order.

Cell enteredPathWhat happens
(0,0)otrie has o, go on
(0,1)oatrie has oa, go on
(1,1)oattrie has oat, go on
(2,1)oath"oath" found and cleared; nodes h, t, a, o pruned on the way back
(1,0)eno neighbor is a, dead end
(1,3)etrie has e, go on
(1,2)eatrie has ea, go on
(1,1)eat"eat" found and cleared; nodes t, a, e pruned on the way back
(2,3)rno neighbor is a, dead end

The search entered 9 cells and returned ["oath", "eat"]. "pea" never starts because the board has no p, and "rain" stops at its first letter.

Java Solution

findWords builds a trie of all words, then starts a backtracking search from every cell that follows the board and the trie together.

  • The node: each Node stores the full word that ends there, so a match is added without rebuilding the string from the path. The children count tells in O(1) whether a node has become a leaf.
  • Marking the path: the cell is set to '#' before the four recursive calls and restored after them. This stops a word from reusing a cell, so ["ab"] with the word "aba" returns an empty list.
  • Clearing found words: node.word = null right after a match means a second path to the same word adds nothing.
  • Pruning: after the recursion, a node with no children and no word is unlinked from its parent and the parent's count drops. The break in the loop stops trying neighbors once every child of the current node is gone.
  • The board afterwards: every '#' is restored, so the caller gets the board back unchanged.

A common mistake is to leave out node.word = null. The word is then added once for every path that spells it. With the board [["a","a"]] and words ["a"], the method returns ["a", "a"] instead of ["a"].

Java
import java.util.ArrayList;
import java.util.List;

public class WordSearchII {
    private static class Node {
        Node[] next = new Node[26];
        int children;   // number of non-null entries in next
        String word;    // the word that ends at this node, or null
    }

    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public List<String> findWords(char[][] board, String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node cur = root;
            for (char ch : w.toCharArray()) {
                int i = ch - 'a';
                if (cur.next[i] == null) {
                    cur.next[i] = new Node();
                    cur.children++;
                }
                cur = cur.next[i];
            }
            cur.word = w;
        }
        List<String> found = new ArrayList<>();
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                dfs(board, r, c, root, found);
            }
        }
        return found;
    }

    private void dfs(char[][] board, int r, int c, Node parent, List<String> found) {
        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return;
        char ch = board[r][c];
        if (ch == '#') return;                    // cell is already on the current path
        Node node = parent.next[ch - 'a'];
        if (node == null) return;                 // no remaining word continues this way
        if (node.word != null) {
            found.add(node.word);
            node.word = null;                     // report each word only once
        }
        board[r][c] = '#';
        for (int[] d : DIRS) {
            if (node.children == 0) break;        // nothing left below this node
            dfs(board, r + d[0], c + d[1], node, found);
        }
        board[r][c] = ch;                         // undo the mark when backtracking
        if (node.children == 0 && node.word == null) {
            parent.next[ch - 'a'] = null;         // prune a branch with no words left
            parent.children--;
        }
    }
}

Complexity

Let m 脳 n be the board size, L the length of the longest word (at most 10), and S the total number of letters in all words.

  • Time: O(S + m 路 n 路 4 路 3^(L-1)). Building the trie touches each letter once. Each of the m 路 n starting cells can open a path of up to L cells, with 4 choices for the first step and at most 3 after that, since the previous cell is marked. Pruning does not change this bound, but it removes most of that work in practice.
  • Space: O(26 路 S) for the trie in the worst case, when words share no prefixes and every letter gets its own node with a 26-slot array. The recursion goes at most L + 1 calls deep, because a call only recurses after matching a trie node.

The method matched a per-word Word Search reference on 20,000 random small boards, and a 12 脳 12 board with 3 脳 10^4 words ran in under 0.1 seconds. A trie search that branches on a wildcard instead of on board cells is Design Add and Search Words Data Structure.