Word Search II
Build a trie from the word list. DFS on the grid: at each cell, follow the trie. If the trie has no child for the current letter, prune that path. When you reach an 'end' node, you've found a word. Much faster than checking each word separately.
How It Works
Searching a grid for many words at once inverts the naive loop: instead of running one DFS per word, build a single trie of the entire word list, then DFS from each grid cell while walking the trie in lockstep. At each step the current trie node's children dictate which neighboring letters are worth exploring — if no child matches, the branch is pruned instantly. Reaching an end-of-word node reports a found word.
The payoff is shared work: all words with a common prefix are matched simultaneously along one DFS path, so the grid is explored once rather than once per word. Two refinements matter in practice: after a word is found, clear its end marker to prevent duplicate reports, and delete trie leaf nodes that have no remaining words below them so dead branches stop attracting exploration. Cell marking (temporarily overwriting with a sentinel) prevents revisiting within one path.
Step-by-Step Visualization
Code
static List<String> findWords(char[][] board, String[] words) {
TrieNode root = buildTrie(words);
List<String> result = new ArrayList<>();
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++)
dfs(board, r, c, root, result);
return result;
}
static void dfs(char[][] board, int r, int c, TrieNode node, List<String> result) {
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return;
char ch = board[r][c];
if (ch == '#' || !node.children.containsKey(ch)) return;
node = node.children.get(ch);
if (node.word != null) { result.add(node.word); node.word = null; }
board[r][c] = '#';
dfs(board, r+1, c, node, result);
dfs(board, r-1, c, node, result);
dfs(board, r, c+1, node, result);
dfs(board, r, c-1, node, result);
board[r][c] = ch;
}Tips & Gotchas
Practice Problems
- 1Word Search II
- 2Word Search
- 3Stream of Characters
About the Advanced Trie Pattern
Extend the basic trie to handle wildcards, combine with DFS for grid search, or store binary representations of numbers for XOR optimization.
Use a trie when you need prefix-based operations that hash maps can't do efficiently — like 'find all words starting with X' or 'find word matching pattern with wildcards'.
Common Trie Interview Problems
- Implement Trie
- Word Search II
- Design Add and Search Words
- Replace Words
- Maximum XOR of Two Numbers
Frequently Asked Questions
Why is the trie approach faster than running Word Search once per word?
Per-word DFS repeats identical grid exploration for every shared prefix — searching for both 'apple' and 'apply' walks 'appl' twice. The trie merges those prefixes so one DFS path checks all words simultaneously, turning k separate O(m*n*4^L) searches into a single traversal bounded by the same term.
What pruning steps keep the DFS from blowing up?
Three are standard: abandon a path the moment the trie has no child for the current letter, unset a word's end flag once found so it is not re-reported, and physically remove childless trie nodes after matches so exhausted branches no longer invite exploration. The node-removal step gives the largest speedup on adversarial inputs.