Word Search II — Trie-Guided Backtracking
Insert all words into a trie and prune DFS paths that are not prefixes, collecting matches as you traverse.
Problem Statement
Given a board and a list of words, return all words that can be formed by sequentially adjacent cells without reusing a cell in a single word.
Why This Problem Matters
- Combines tries with grid backtracking for efficient pruning.
- Highlights how to share traversal work across many target words.
- Demonstrates advanced search optimisation expected in senior interviews.
Thought Process
Build a trie of target words
Each node stores children and optional word field to mark completion.
DFS with pruning
Only continue exploring if the current prefix exists in the trie.
Avoid duplicates
Once a word is found, mark it as null to prevent repeated additions.
Step-by-Step Reasoning
- Insert all words into trie nodes with word references at terminal nodes.
- For each board cell, DFS using trie children, marking visited via in-place mutation.
- When trie node has a word, add to result and null out to avoid duplication.
- Backtrack by restoring characters after exploring neighbors.
Dry Run
board = [[o,a,a,n],[e,t,a,e],[i,h,k,r],[i,f,l,v]], words = ["oath","pea","eat","rain"]
DFS finds "oath" and "eat" while pruning invalid paths.
Word already found
Trie node word set to null so duplicates are skipped.
Complexity Analysis
Time
O(M·4^L)
Space
O(T)
Why
M board cells explored with branching limited by trie; T is total characters across words.
Annotated Solution
import java.util.ArrayList;
import java.util.List;
public class WordSearchII {
private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = buildTrie(words);
List<String> result = new ArrayList<>();
for (int r = 0; r < board.length; r += 1) {
for (int c = 0; c < board[0].length; c += 1) {
dfs(board, r, c, root, result);
}
}
return result;
}
private void dfs(char[][] board, int r, int c, TrieNode node, List<String> result) {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) {
return;
}
char ch = board[r][c];
if (ch == '#' || node.children[ch - 'a'] == null) {
return;
}
node = node.children[ch - 'a'];
if (node.word != null) {
result.add(node.word);
node.word = null;
}
board[r][c] = '#';
for (int[] dir : DIRS) {
dfs(board, r + dir[0], c + dir[1], node, result);
}
board[r][c] = ch;
}
private TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
int idx = ch - 'a';
if (node.children[idx] == null) {
node.children[idx] = new TrieNode();
}
node = node.children[idx];
}
node.word = word;
}
return root;
}
private static class TrieNode {
TrieNode[] children = new TrieNode[26];
String word;
}
}Trie nodes store words at leaves to avoid string concatenation; DFS prunes invalid branches early by checking child existence.
Common Pitfalls
- Not pruning on trie nodes causes exponential blow-up.
- Failing to mark visited cells leads to incorrect reuse.
- Returning duplicates if you do not null out word after adding.
Follow-Up Questions
- How would you handle thousands of queries with dynamic word additions?
- Can you optimise further by removing dead trie branches once exhausted?