Definition
Word Search II combines a Trie data structure with grid DFS backtracking.
- Trie construction inserts all dictionary words so shared prefixes are tested together.
- DFS with Trie pointer walks the grid and advances the Trie pointer in lock-step.
- Prefix pruning stops any path whose prefix no dictionary word shares, avoiding dead-end exploration.
- Word collection stores the complete word on the terminal Trie node for O(1) retrieval.
- Leaf pruning optionally removes Trie nodes after a word is found to shrink the tree during search.
Think of a grid of letters on a fraud-detection heat map and a watchlist of suspicious code words. Instead of hunting for each watchlist word separately, you build one big index of all the words and sweep the grid once. At each cell you check the index: if the letters walked so far are not the start of any watchlist word, you abandon that path immediately.
Understanding the Concepts
What is the Word Search II Problem?
Given an m x n board of characters and a list of words, return all words that can be formed by sequentially adjacent cells (horizontally or vertically neighboring), where each cell is used at most once per word. This is the multi-word extension of Word Search.
At National Bank of India, the compliance team maintains a watchlist of coded fraud patterns and needs to find every pattern embedded in a character grid pulled from transaction data.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class WordSearchII {
static class TrieNode {
TrieNode[] children = new TrieNode[26];
String word = null; // store complete word at terminal node
}
public static List<String> findWords(char[][] board, String[] words) {
// Build Trie
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode node = root;
for (char c : w.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) node.children[idx] = new TrieNode();
node = node.children[idx];
}
node.word = w;
}
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;
}
private 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[ch - 'a'] == null) return; // visited or no prefix
node = node.children[ch - 'a'];
if (node.word != null) {
result.add(node.word);
node.word = null; // avoid duplicates
}
board[r][c] = '#'; // mark visited
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; // backtrack
}
public static void main(String[] args) {
char[][] board = {
{'o', 'a', 'a', 'n'},
{'e', 't', 'a', 'e'},
{'i', 'h', 'k', 'r'},
{'i', 'f', 'l', 'v'}
};
String[] words = {"oath", "pea", "eat", "rain"};
System.out.println("Found: " + findWords(board, words));
}
}
Found: [oath, eat]
Why Is the Trie Approach Better Than Per-Word Search?
Without a Trie, we would run a separate DFS for each word in the dictionary, repeating enormous amounts of work. With a Trie, shared prefixes are tested together in a single grid sweep. If words "oath" and "oat" share the prefix "oa", the Trie explores that prefix only once.
package com.bank.core;
public class TrieVsPerWord {
// Per-word approach: O(W * m * n * 4^L) where W = number of words
// Trie approach: O(m * n * 4^L) total, shared prefixes tested once
// For W = 1000 words, the Trie approach is orders of magnitude faster
}
How Does the Trie Construction Work?
We insert every dictionary word into a single Trie. Each node has 26 children for lowercase English letters. At the terminal node of each word, we store the complete word string so collection is immediate without reconstructing the word from the path.
package com.bank.core;
public class TrieConstruction {
static class TrieNode {
TrieNode[] children = new TrieNode[26];
String word = null;
}
public static TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode node = root;
for (char c : w.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
node.children[idx] = new TrieNode();
}
node = node.children[idx];
}
node.word = w; // store complete word for O(1) collection
}
return root;
}
}
How Does the DFS Walk the Trie?
The DFS carries a Trie pointer alongside the grid position. Before entering a cell, it checks whether the cell's character is a child of the current Trie node. If not, the entire branch is pruned because no dictionary word has this prefix. This is the key optimization.
package com.bank.core;
public class TrieWalkExplained {
// At each cell:
// 1. Check if cell char is a child of current Trie node
// -> if null, PRUNE (no dictionary word has this prefix)
// 2. Advance Trie pointer to the child
// 3. Check if this node has a complete word -> collect it
// 4. Mark cell visited, recurse into 4 neighbors
// 5. Restore cell (backtrack)
}
How Is This Different from Word Search?
| Aspect | Word Search | Word Search II |
|---|---|---|
| Input | One word | List of words |
| Data structure | None | Trie for all words |
| Grid sweeps | One per starting cell per word | One total sweep |
| Pruning | Character mismatch | Trie prefix (much stronger) |
| Output | Boolean (found/not found) | List of found words |
| Duplicate prevention | Not needed | Null out word field after collection |
What Are Common Mistakes?
The first mistake is running a separate DFS for each word without a Trie, which is correct but too slow for large dictionaries. The second is forgetting to null out the word field after collection, which causes the same word to be added multiple times.
// WRONG: word collected multiple times
if (node.word != null) {
result.add(node.word);
// BUG: node.word still set, will be collected again from another path
}
// CORRECT: clear after collection
if (node.word != null) {
result.add(node.word);
node.word = null; // prevent duplicate collection
}
What About Trie Leaf Pruning?
An advanced optimization is to prune Trie leaf nodes after their word has been collected. If a Trie node has no children and its word is null, it serves no purpose and can be removed. This shrinks the Trie as the search proceeds, making later DFS calls faster.
package com.bank.core;
public class TrieLeafPruning {
// After collecting a word and exploring children:
// Check if the child Trie node is now a leaf with no word
// If so, set children[idx] = null to prune
// This optimization matters when the dictionary is large
}
What About Time and Space Complexity?
The worst-case time is O(m * n * 4^L) where L is the maximum word length. However, the Trie pruning makes the practical cost far smaller because dead prefixes are abandoned immediately. The space is O(total characters in dictionary) for the Trie plus O(L) for the recursion stack.
package com.bank.core;
public class WordSearchIIComplexity {
// Time: O(m * n * 4^L) worst case
// Practical: much faster due to Trie prefix pruning
// Space: O(sum of word lengths) for Trie + O(L) recursion depth
// L = maximum word length
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask:
- Implement the Trie from scratch (TrieNode class, insert, search, startsWith).
- Why store the full word on the terminal node instead of a boolean flag? For O(1) collection without path reconstruction.
- How would you handle uppercase and special characters? Expand the children array or use a HashMap.
- What if the dictionary is dynamic (words added during search)? The Trie supports incremental insertion.
package com.bank.core;
public class TrieOperations {
static class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd = false;
String word = null;
}
public static boolean search(TrieNode root, String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) return false;
node = node.children[c - 'a'];
}
return node.isEnd;
}
}
Visual Overview
Trie for words ["oath", "oat", "eat"]:
root
├── o
│ └── a
│ └── t (word: "oat")
│ └── h (word: "oath")
└── e
└── a
└── t (word: "eat")
DFS on Grid with Trie:
┌───┬───┬───┬───┐
│ o │ a │ a │ n │ Trie pointer starts at root
├───┼───┼───┼───┤ Cell 'o' -> root has child 'o' -> advance
│ e │ t │ a │ e │ Cell 'a' -> 'o' has child 'a' -> advance
├───┼───┼───┼───┤ Cell 't' -> 'a' has child 't' -> advance
│ i │ h │ k │ r │ node.word = "oat" -> COLLECT
├───┼───┼───┼───┤ Cell 'h' -> 't' has child 'h' -> advance
│ i │ f │ l │ v │ node.word = "oath" -> COLLECT
└───┴───┴───┴───┘
Key Takeaway
Word Search II asks for every dictionary word that can be traced through adjacent cells of a grid, each cell used at most once per word. The naive approach runs a separate grid search for each word, which repeats enormous amounts of work. My efficient solution builds one Trie from all the words so their shared prefixes are tested together, then sweeps the grid a single time with a depth-first backtracking search that walks a Trie pointer in lock-step with the grid path.
Before stepping into a cell, I check whether its character is a child of the current Trie node, and if not I abandon the path immediately. This pruning is the whole reason the single-Trie approach wins. When the Trie pointer reaches a node whose stored word field is set, I collect that word and clear the field so the same word is not reported twice. I mark the cell visited before recursing into its four neighbors and restore it on the way back.
The details interviewers look for are sharing one Trie across all words rather than one per word, storing the full word string on the terminal node for constant-time collection, and the correct mark-and-restore to enforce the use-each-cell-once rule per path.
In my project at National Bank of India, I applied this to a fraud-pattern grid where flagged activity is encoded as a character matrix and compliance keeps a watchlist of coded patterns. Building one Trie from the whole watchlist let me find every embedded pattern in a single sweep.
Remember one sentence: build one Trie from all words, DFS the grid with a Trie pointer, prune dead prefixes, and collect words at terminal nodes.
---