Hardtrie
Word Search II
Problem (restated)
Board of letters and a word list. Return all words that can be formed by adjacent (4-dir) cells without reusing a cell in one word.
Intuition
Insert all words into a trie. DFS from every cell following trie edges; record word at End and clear to avoid duplicates; prune empty subtrees.
Approaches
Trie + board DFS prune
Tested onlyTime O(m·n·4·L)Space O(Σ L)
Idea. Mark cell ‘#’, recurse 4 dirs, restore. Delete dead trie nodes after exploration.
Walkthrough. Board o a a n / e t a e / i h k r / i f l v with words [“oath”,“pea”,“eat”,“rain”] → [“eat”,“oath”].
Trade-offs. Per-word LC79 is too slow for many words; shared prefix trie wins.
Solution
type Node = { children: Map<string, Node>; word: string | null };
export function findWords(board: string[][], words: string[]): string[] {
const root: Node = { children: new Map(), word: null };
for (const w of words) {
let n = root;
for (const c of w) {
if (!n.children.has(c)) n.children.set(c, { children: new Map(), word: null });
n = n.children.get(c)!;
}
n.word = w;
}
const res: string[] = [];
const m = board.length, nCols = board[0]!.length;
const dfs = (r: number, c: number, node: Node) => {
const ch = board[r]![c]!;
const next = node.children.get(ch);
if (!next) return;
if (next.word) {
res.push(next.word);
next.word = null;
}
board[r]![c] = "#";
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]] as const) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < nCols && board[nr]![nc] !== "#") dfs(nr, nc, next);
}
board[r]![c] = ch;
if (next.children.size === 0) node.children.delete(ch);
};
for (let r = 0; r < m; r++) for (let c = 0; c < nCols; c++) dfs(r, c, root);
return res;
}
type Node = { children: Map<string, Node>; word: string | null };
export function findWords(board: string[][], words: string[]): string[] {
const root: Node = { children: new Map(), word: null };
for (const w of words) {
let n = root;
for (const c of w) {
if (!n.children.has(c)) n.children.set(c, { children: new Map(), word: null });
n = n.children.get(c)!;
}
n.word = w;
}
const res: string[] = [];
const m = board.length, nCols = board[0]!.length;
const dfs = (r: number, c: number, node: Node) => {
const ch = board[r]![c]!;
const next = node.children.get(ch);
if (!next) return;
if (next.word) {
res.push(next.word);
next.word = null;
}
board[r]![c] = "#";
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]] as const) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < nCols && board[nr]![nc] !== "#") dfs(nr, nc, next);
}
board[r]![c] = ch;
if (next.children.size === 0) node.children.delete(ch);
};
for (let r = 0; r < m; r++) for (let c = 0; c < nCols; c++) dfs(r, c, root);
return res;
}
Template connection
Trie-guided grid backtracking.
Reflection
- Which pattern gave this away within 90 seconds?
- What changed from the standard template?
- What would break the current solution?