Definition
- Word Search II – finds all dictionary words that can be formed by adjacent-cell paths in a character grid without reusing any cell.
- Trie acceleration – loading all words into a trie lets the DFS explore all words simultaneously, pruning the moment no word shares the current prefix.
- DFS with backtracking – from each cell, descend the trie by the cell's character; mark cells visited during recursion and restore on backtrack.
- Word storage – store the complete word at terminal trie nodes to avoid reconstructing it from the path.
- Complexity – bounded by grid size times the longest word length, but trie pruning makes it much faster in practice.
The National Bank of India scans a grid of characters extracted from a scanned cheque region to spot known keywords like SALARY or RENT along connected cells. A trie of keywords lets the scan follow all keywords at once and stop early on dead-end prefixes.
Understanding the Concepts
What is the Word Search with a Trie problem?
Given an m x n grid of characters and a list of dictionary words, find all words that can be formed by tracing a path of adjacent cells (up, down, left, right) without reusing any cell in the same path. For example, if the grid contains the letters S, A, L, A, R, Y along a connected path, and "SALARY" is in the dictionary, it should be found.
package com.bank.core;
// Grid: Dictionary: ["SALARY", "RENT", "LOAN"]
// S A L
// R E N
// T O A
// "SALARY" is NOT findable (no connected path)
// "RENT" -> R(1,0) E(1,1) N(1,2) T(2,0)? T is not adjacent to N
// Depends on actual adjacency
Why use a trie instead of searching word by word?
Searching for each word separately requires a full DFS per word, which is wasteful because many words share common prefixes. A trie lets you search for all words simultaneously: at each step in the DFS, you follow the trie to check whether any word continues with this prefix. If no word does, you prune immediately. This shared traversal is far more efficient.
package com.bank.core;
// Without trie: separate DFS for each of 1000 words -> very slow
// With trie: one shared DFS, each step checks the trie
// If prefix "SAL" has no continuation, prune ALL words starting with "SAL"
// Trie shares prefix work across all words
How do you build the trie?
Insert each dictionary word into the trie character by character. At each terminal node (end of a word), store the complete word string so you can add it to the result without path reconstruction.
package com.bank.service;
public class TrieNode {
TrieNode[] children = new TrieNode[26];
String word = null; // stored at terminal nodes
}
public class WordSearchTrie {
private TrieNode root = new TrieNode();
private void buildTrie(String[] words) {
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;
}
}
}
How does the DFS work with the trie?
From each cell, start a DFS carrying the current trie node. At the cell, check if the trie node has a child for the cell's character. If not, prune: no word continues with this prefix. If yes, descend to that child. If the child is marked as a complete word, add it to the result. Mark the cell visited, recurse into the four adjacent cells, then restore the cell.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class WordSearchWithTrie {
private TrieNode root = new TrieNode();
private List<String> result = new ArrayList<>();
public List<String> findWords(char[][] board, String[] words) {
buildTrie(words);
int rows = board.length;
int cols = board[0].length;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
dfs(board, r, c, root);
}
}
return result;
}
private void dfs(char[][] board, int r, int c, TrieNode node) {
if (r < 0 || r >= board.length
|| c < 0 || c >= board[0].length) return;
char ch = board[r][c];
if (ch == '#') return; // already visited
TrieNode child = node.children[ch - 'A'];
if (child == null) return; // no word continues with this prefix
if (child.word != null) {
result.add(child.word);
child.word = null; // avoid duplicates
}
board[r][c] = '#'; // mark visited
dfs(board, r + 1, c, child);
dfs(board, r - 1, c, child);
dfs(board, r, c + 1, child);
dfs(board, r, c - 1, child);
board[r][c] = ch; // restore
}
private void buildTrie(String[] words) {
for (String w : words) {
TrieNode node = root;
for (char ch : w.toCharArray()) {
int idx = ch - 'A';
if (node.children[idx] == null) {
node.children[idx] = new TrieNode();
}
node = node.children[idx];
}
node.word = w;
}
}
public static void main(String[] args) {
WordSearchWithTrie solver = new WordSearchWithTrie();
char[][] board = {
{'S', 'A', 'L'},
{'A', 'R', 'Y'},
{'E', 'N', 'T'}
};
String[] words = {"SALARY", "RENT", "SAR", "SALE"};
System.out.println(solver.findWords(board, words));
}
}
[SAR]
Why mark cells with '#' and restore them?
The no-reuse rule means a cell cannot appear twice in the same path. Marking the cell with a sentinel character like # during recursion prevents revisiting it. Restoring the original character after recursion allows other paths starting from different cells to use it.
package com.bank.core;
// Mark: board[r][c] = '#' prevents re-entering this cell
// Restore: board[r][c] = ch allows other starting paths to use it
// This is the standard backtracking visited-cell technique
How do you avoid duplicate words in the result?
The same word might be found via different paths in the grid. To avoid duplicates, set child.word = null after adding it to the result the first time. This ensures each word is only collected once.
package com.bank.core;
// First time finding "SAR":
if (child.word != null) {
result.add(child.word); // add "SAR"
child.word = null; // prevent adding again
}
// Second path to "SAR": child.word is null, skip
What are the edge cases?
Edge cases include: no words found, single-cell grid, word longer than the grid can accommodate, duplicate words in the dictionary, and words that share prefixes.
package com.bank.core;
// Edge case 1: no words match any path -> empty result
// Edge case 2: 1x1 grid with 'A', words=["A"] -> ["A"]
// Edge case 3: word "ABCDEFGHIJ" in a 3x3 grid -> impossible (only 9 cells)
// Edge case 4: words=["SAL","SAL"] -> trie deduplicates, found at most once
// Edge case 5: words=["SAL","SALARY"] -> trie shares prefix, both can be found
What about a banking use case?
At the National Bank of India, Rajesh scans a grid of characters extracted from a cheque image to detect known keywords like SALARY, RENT, and LOAN along connected cell paths, helping classify the cheque's purpose.
package com.bank.service;
import java.util.List;
public class ChequeKeywordScanner {
public void scanCheque(char[][] grid, String[] keywords) {
WordSearchWithTrie solver = new WordSearchWithTrie();
List<String> found = solver.findWords(grid, keywords);
if (found.isEmpty()) {
System.out.println("No keywords detected");
} else {
System.out.println("Detected keywords: " + found);
}
}
}
What should a senior engineer know?
A senior engineer should know that trie pruning is an optimization that can be enhanced further by removing trie branches once all words in a subtree have been found (trie pruning optimization). This prevents re-exploring dead subtrees and significantly speeds up dense grids. The worst-case complexity is O(m * n * 4^L) where L is the maximum word length, but trie pruning makes the practical performance much better.
package com.bank.core;
// Senior optimizations:
// 1. Trie branch pruning: remove children once all words found
// 2. Null-out word to avoid duplicates
// 3. Mark cells in-place with '#' instead of using a boolean[][] visited
// 4. Worst case: O(m*n*4^L) but trie pruning makes it much faster
// 5. Store full word at terminal to avoid path reconstruction
Visual Overview
Trie + DFS on grid:
Grid: Trie (words: SAR, SALE):
S A L
A R Y root
E N T /
S
|
A
/ \
R L
| |
[SAR] E
|
[SALE]
DFS from cell (0,0) = 'S':
┌──────────────────────────────────────────┐
│ Trie: root -> S child exists │
│ Move to trie node S │
│ │
│ Try neighbors: (0,1)='A' │
│ Trie: S -> A child exists │
│ Move to trie node A │
│ │
│ Try neighbors: (1,1)='R' │
│ Trie: A -> R child exists │
│ Move to trie node R │
│ R has word="SAR" -> add to result! │
│ │
│ R has no more children -> stop this path │
│ Backtrack, try (0,2)='L' │
│ Trie: A -> L child exists │
│ Move to trie node L │
│ Try neighbors for 'E'... │
└──────────────────────────────────────────┘
Key: the trie prunes paths where no word
continues, avoiding unnecessary exploration.
Key Takeaway
Word Search with a Trie combines backtracking grid traversal with the Trie pattern to find all dictionary words that can be traced along adjacent cell paths without reusing a cell. Loading all words into a trie lets the DFS explore all words simultaneously: at each cell, the trie tells you whether any word continues with this prefix, and if not, the path is pruned immediately.
The DFS starts from each grid cell, carrying the current trie node. At each step, you check if the trie node has a child for the cell's character. If it does, you descend; if the child is a complete word, you add it to the result and null out the word to prevent duplicates. You mark the cell visited during recursion and restore it on backtrack so other paths can reuse it.
The trie is what makes this approach dramatically faster than searching for each word separately. Without a trie, you would need a full DFS for each dictionary word, duplicating work across words that share prefixes. With a trie, the shared prefix work is done once, and dead-end prefixes are pruned immediately. A senior optimization is to remove trie branches once all words in a subtree have been found, preventing re-exploration of exhausted subtrees.
At the National Bank of India, Rajesh scanned character grids extracted from cheque images to detect known keywords along connected cell paths. The trie of keywords let the scan follow all keywords at once, and the backtracking visited-cell technique enforced the no-reuse rule. The trie pruning kept the scan fast even with large keyword dictionaries.
Remember one sentence: walk the grid and the trie together, pruning any path whose prefix matches no word, and mark cells visited during recursion to enforce the no-reuse rule.
---