Tries · LC #212
Word Search II
Find all words from a dictionary that exist in an m×n character board using DFS+Trie: build a trie of all words, then DFS from every cell, pruning branches not in the trie.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an m×n board of characters and a list of strings `words`, return all words found in the board. A word is formed by sequentially adjacent cells (4-directional), and the same cell may not be used more than once per word.
Sample I/O
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"]Intuition
How to Think About It
Intuition
Running a separate DFS for each word would be O(W · M · N · 4^L) - too slow. By building a trie of all words first, a single board-DFS simultaneously searches all words: whenever the current board path cannot extend any trie branch, we prune immediately.
Core Concept
Insert all words into a trie, storing the full word string at the terminal node. From every board cell, run DFS: follow the trie child matching the current cell character. If no child exists, return immediately. When a terminal node is reached, collect the word and null out its marker to avoid duplicates. Restore board cells after DFS (backtrack). Optionally prune empty trie subtrees bottom-up for large inputs.
When to use
Multi-pattern search on a grid where patterns share prefixes - the trie collapses redundant prefix traversals. Classic hard interview problem at FAANG.
When NOT to use
Single-word board search (LC 79) - standard DFS suffices. When the word list is tiny (< ~5 words), the trie overhead is not worth it.
Key Insights
What to Know Cold
- The trie converts multi-word search into a single board traversal - all prefix-sharing words are checked simultaneously.
- Storing the word string at the terminal trie node avoids reconstructing it from the DFS path.
- Setting `node.word = null` after collecting a word provides O(1) deduplication without a separate set.
- Marking the board cell as `#` during DFS prevents revisiting - restore it on backtrack.
- Bottom-up trie pruning (remove leaf nodes after collecting their word) dramatically speeds up repeated boards with many words.
1 example
Worked Examples
Finding "eat" and "oath" on a 4×4 board
Board has scattered chars; trie prunes mismatches instantly.
Build trie from ["oath","pea","eat","rain"]. DFS from (1,0)="e": follows e→a→t, finds "eat". From (0,0)="o": follows o→a→t→h, finds "oath".
const board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]; findWords(board, ["oath","pea","eat","rain"]); // ["eat","oath"]
Trie pruning means "pea" and "rain" are rejected at first character - no wasted DFS depth.