Word Search II
The Prompt
Given an `m x n` `board` of characters and a list of strings `words`, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Understanding the Problem
Running Word Search once per dictionary word repeats the same board exploration over and over — words like "oath" and "oat" would each re-walk the same cells. The fix is to search for all words simultaneously: build one trie from the dictionary, then run a single DFS from every board cell, moving through the trie in lockstep with the board.
At each step the current trie node tells you which next letters are worth pursuing: if the neighboring cell's letter is not a child of the current node, no dictionary word continues that way, so the branch is pruned instantly. Whenever the walk lands on a node with an end flag, a complete word has been spelled — record it.
The Interview Flow
Interviewer
This combines Word Search I and Tries. Given a board and a dictionary of words, how do you find all the words from the dictionary that are on the board?
Candidate
If I just ran Word Search I for every single word in the dictionary, it would be very inefficient, especially if the dictionary is large.
Interviewer
Exactly. How can a Trie help here?
Candidate
I can build a Trie from all the words in the dictionary. This way, all the words are stored in a consolidated prefix structure. Then, I can perform a single DFS/backtracking search on the board.
Interviewer
How does the DFS work with the Trie?
Candidate
I would start a DFS from every cell on the board. The DFS function would take the current cell, the current node in the Trie, and the path/word built so far. At each cell, I check if the character exists as a child of the current Trie node. If it doesn't, this path is not a prefix of any word, so I can prune the search and backtrack. If it does, I move to that child in the Trie.
Interviewer
How do you know when you've found a complete word?
Candidate
If the Trie node I just moved to is marked as an "end of word", I've found a valid word from the dictionary. I add it to my result set. I don't stop the search, though, because this word could be a prefix for a longer word (e.g., finding "app" and then "apple"). To avoid adding the same word multiple times, I can clear the "end of word" flag after finding it.
Interviewer
That's a highly optimized approach. It prunes the search space very effectively. Please implement it.
Why does one trie-guided DFS beat searching word by word?
The invariant: the DFS is at cell (r, c) with trie node t exactly when the letters along the current path spell a prefix of at least one dictionary word, and t is that prefix's node. Extending the path only into children of t preserves this — so every explored path is a live prefix, and dead prefixes cost zero work.
Backtracking marks a cell used on the way down and restores it on the way up, so no word reuses a cell. Building the trie is O(total characters); the search is O(m · n · 4 · 3^(L−1)) in the worst case for max word length L — but the trie pruning is what makes it fast in practice, cutting off most branches after one or two letters.
Trie + Backtracking (DFS)
- **1. Build the Trie:**
- - Create a Trie and insert all the `words` from the dictionary into it.
- **2. Backtracking Search:**
- - Initialize a `result` set to store found words (a set handles duplicates automatically).
- - Iterate through every cell `(r, c)` on the `board` to start a DFS search.
- - **DFS Helper `dfs(r, c, node, word)`:**
- - Takes current coordinates `(r,c)`, current Trie `node`, and the `word` built so far.
- - Base cases: Check for out-of-bounds, or if the character `board[r][c]` is not a child of the current Trie `node`. If so, return.
- - Move to the next node in the trie: `node = node.children[board[r][c]]`.
- - Append the character to the current word path.
- - Check for completion: If `node.isEndOfWord`, add the word to the `result` set and mark `node.isEndOfWord = false` to prevent re-adding.
- - Mark the board cell as visited (e.g., `board[r][c] = '#'`).
- - Recursively call `dfs` on all four neighbors.
- - Backtrack: Restore the character on the board.
- Finally, convert the `result` set to a list and return it.
Try it yourself
Write your solution and run it against 2 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function findWords(board, words) {
const root = {};
for (const word of words) {
let node = root;
for (const char of word) {
if (!node[char]) node[char] = {};
node = node[char];
}
node.word = word;
}
const res = [];
const rows = board.length, cols = board[0].length;
function dfs(r, c, node) {
const char = board[r][c];
if (char === '#' || !node[char]) return;
node = node[char];
if (node.word) {
res.push(node.word);
node.word = null; // Avoid duplicates
}
board[r][c] = '#';
if (r > 0) dfs(r - 1, c, node);
if (r < rows - 1) dfs(r + 1, c, node);
if (c > 0) dfs(r, c - 1, node);
if (c < cols - 1) dfs(r, c + 1, node);
board[r][c] = char; // Backtrack
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
dfs(r, c, root);
}
}
return res;
}Explanation
Board [["o","a"],["h","t"]] with words ["oath", "at"] — one traversal finds both.
1Build the trie from ["oath", "at"]: two branches, o → a → t → h and a → t, with end flags on h and the second t. This one structure will guide the search for both words at once.
2DFS from cell (0,0): 'o' is a child of the root, so descend. Neighbors continue o → a → t → h, each step matched by a trie child, and h carries an end flag — record "oath". All four cells are used exactly once.
3DFS from cell (0,1): 'a' matches the root's other branch, and neighbor (1,1) gives a → t with an end flag — record "at". Starts at 'h' and 't' die at the root (no such children), pruned before exploring anything.
Complexity Analysis
TIME
O(m*n*4^L)
SPACE
O(W*L)
Finished working through this one?
Mark it complete to track it on your Data Structures path.