Word Search II
You are given an m x nboardwords
Limits: 1 <= m, n <= 121 <= words.length <= 3 * 10^41 <= words[i].length <= 10
Example 1
Output: ["oath","eat"]
Example 2
Output: []
How to Think About It
Step 1: One word at a time is too slow
For a single word this is
Step 2: Search for all words at once
Put every word into a trie, as in chch
- 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 oper
| Cell entered | Path | What happens |
|---|---|---|
| (0,0) | o | trie has o, go on |
| (0,1) | oa | trie has oa, go on |
| (1,1) | oat | trie has oat, go on |
| (2,1) | oath | "oath" found and cleared; nodes h, t, a, o pruned on the way back |
| (1,0) | e | no neighbor is a, dead end |
| (1,3) | e | trie has e, go on |
| (1,2) | ea | trie has ea, go on |
| (1,1) | eat | "eat" found and cleared; nodes t, a, e pruned on the way back |
| (2,3) | r | no neighbor is a, dead end |
The search entered 9 cells and returned ["oath", "eat"]
Java Solution
findWords
- The node: each
stores the fullNode that ends there, so a match is added without rebuilding the string from the path. Theword count tells in O(1) whether a node has become a leaf.children - 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'#' with the word["ab"] returns an empty list."aba" - Clearing found words:
right after a match means a second path to the same word adds nothing.node.word = null - Pruning: after the recursion, a node with no children and no word is unlinked from its parent and the parent's count drops. The
in the loop stops trying neighbors once every child of the current node is gone.break - The board afterwards: every
is restored, so the caller gets the board back unchanged.'#'
A common mistake is to leave out node.word = null[["a","a"]]["a"]["a", "a"]["a"]
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