212. Word Search II
hardAsked at PinterestWord Search II is Pinterest's canonical 'trie + grid DFS' problem and a feared L5 onsite. Given a 2D board and a list of dictionary words, return every word found by walking adjacent cells without reuse. The trick is sharing the dictionary across DFS attempts.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Pinterest loops.
- Glassdoor (2026-Q1)— Pinterest L5 onsite reports cite Word Search II as the hard graph / trie round.
- LeetCode Pinterest tag (2026-Q1)— On the Pinterest company-tagged problem list as one of the highest-difficulty entries.
- Blind (2025-12)— Pinterest senior IC onsite reports describe this as a 45-minute trie-DFS problem.
Problem
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.
Constraints
m == board.lengthn == board[i].length1 <= m, n <= 12board[i][j] is a lowercase English letter.1 <= words.length <= 3 * 10^41 <= words[i].length <= 10All the strings of words are unique.
Examples
Example 1
board = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']], words = ['oath','pea','eat','rain']['eat','oath']Approaches
1. DFS per word (brute force)
For each word, scan every cell as a possible start. DFS to verify the word.
- Time
- O(W * m * n * 4^L)
- Space
- O(L) recursion
function findWordsBrute(board, words) {
const rows = board.length, cols = board[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function dfs(r, c, word, idx) {
if (idx === word.length) return true;
if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
if (board[r][c] !== word[idx]) return false;
const tmp = board[r][c];
board[r][c] = '#';
for (const [dr, dc] of dirs) {
if (dfs(r + dr, c + dc, word, idx + 1)) {
board[r][c] = tmp;
return true;
}
}
board[r][c] = tmp;
return false;
}
const out = [];
for (const word of words) {
let found = false;
outer: for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(r, c, word, 0)) { found = true; break outer; }
}
}
if (found) out.push(word);
}
return out;
}Tradeoff: Correct but slow: 30,000 words * 12*12 starts * 4^10 = blows the time limit. Anchor with this, then upgrade.
2. Trie of all words + single DFS (optimal)
Insert every word into a trie. Then DFS each cell as a start, but instead of pursuing one word, walk the trie in parallel. When trie-walk hits an isEnd, record the word.
- Time
- O(m * n * 4^L) — independent of W
- Space
- O(W * L) for the trie
class TrieNode {
constructor() {
this.children = new Map();
this.word = null;
}
}
function findWords(board, words) {
const root = new TrieNode();
for (const w of words) {
let node = root;
for (const ch of w) {
if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
node = node.children.get(ch);
}
node.word = w;
}
const rows = board.length, cols = board[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const out = [];
function dfs(r, c, node) {
if (r < 0 || c < 0 || r >= rows || c >= cols) return;
const ch = board[r][c];
if (ch === '#' || !node.children.has(ch)) return;
const next = node.children.get(ch);
if (next.word !== null) {
out.push(next.word);
next.word = null; // dedup
}
board[r][c] = '#';
for (const [dr, dc] of dirs) dfs(r + dr, c + dc, next);
board[r][c] = ch;
// Optional pruning: if next has no children left, splice it out
if (next.children.size === 0) node.children.delete(ch);
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) dfs(r, c, root);
}
return out;
}Tradeoff: Decouples search cost from word count. The optional 'splice leaf nodes' pruning ensures the trie shrinks as words are found, giving real speedup on average inputs. This is the textbook answer at Pinterest.
Pinterest-specific tips
Pinterest L5 interviewers want THREE upgrades over the brute force: (1) trie to share prefix walks; (2) setting word=null on find to dedupe (you don't want 'oath' returned twice if the grid has two 'o' starts); (3) leaf-pruning to shrink the trie as you go. Volunteer pruning before they ask — it's the signal that separates strong L4 from L5.
Common mistakes
- Forgetting to mark cells visited (board[r][c] = '#') during DFS — same letter gets reused.
- Not restoring the cell on backtrack — corrupts the board for subsequent DFS starts.
- Returning duplicates because the same word is reachable from multiple starts — set word=null after recording.
- Storing the word ONLY at the trie node and walking back up — fine but slower than storing it inline.
Follow-up questions
An interviewer at Pinterest may pivot to one of these next:
- What if the same letter CAN be reused? (Easier — drop the visited marker.)
- Add diagonal moves (8-directional).
- Word Search III: count distinct words instead of returning them.
- Streaming: words arrive after the board is fixed — preprocess what?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is the trie approach independent of word count?
All words share the trie prefix walk. When DFS visits cell (r, c), it walks the trie ONCE regardless of how many words pass through that prefix. The board traversal is the bottleneck, not the dictionary size.
Is leaf-pruning a real-world optimization?
Yes — it keeps the trie depth tight as words are removed. On dense inputs it can halve runtime. Mention it even if you don't implement it under time pressure.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill Word Search II and other Pinterest interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →