—cell (r,c)
Find every word from a dictionary that can be spelled along adjacent cells of a grid. Instead of searching the board once per word, build a trie of all words and run a single backtracking DFS that walks board letters and trie edges in lockstep, pruning the instant a prefix dies.
Given an m×n grid of letters and a list of words, return all words that can be formed by a path of horizontally or vertically adjacent cells, where no cell is reused within a single word. For board = [oaan; etae; ihkr; iflv] and words = [oath, pea, eat, rain], the answer is [oath, eat] — oath snakes o→a→t→h and eat is e→a→t, while pea and raincan't be traced.
trie and DFS the board once, descending the trie as you step. The trie collapses shared prefixes (eat and eats share eat), and the moment the current board letter has no matching trie child, that whole branch is dead — prune immediately.node.children.get(board[r][c]). If it's missing, return — why: no dictionary word continues with this letter, so the branch is hopeless.Set.#), recurse into the 4 neighbors, then restore it — why: backtracking frees the cell for other paths.dfs(r, c, root) for every cell. The very first children.get against rootrejects any cell whose letter isn't the first letter of some word, so non-starts cost almost nothing.With the trie, board traversal is bounded by the grid and the longest word length L (after the first step only 3 directions are new), independent of how many words share a prefix. Trie space is O(total letters in words). A common extra optimization: prune leaf trie nodes after their word is found so the trie shrinks as you go.
oath, pea, eat, rain, then DFS the board following only letters that exist as trie edges.—∅{ }interface TrieNode {
children: Map<string, TrieNode>;
word: string | null; // non-null only at the end of a word
}
function findWords(board: string[][], words: string[]): string[] {
// 1. Build a trie of all target words.
const root: TrieNode = { children: new Map(), word: null };
for (const w of words) {
let node = root;
for (const ch of w) {
if (!node.children.has(ch)) {
node.children.set(ch, { children: new Map(), word: null });
}
node = node.children.get(ch)!;
}
node.word = w; // mark terminal
}
const rows = board.length;
const cols = board[0].length;
const found: string[] = [];
function dfs(r: number, c: number, node: TrieNode): void {
const ch = board[r][c];
const next = node.children.get(ch);
if (!next) return; // prune: no word continues here
if (next.word !== null) { // reached a complete word
found.push(next.word);
next.word = null; // de-dupe without a Set
}
board[r][c] = '#'; // mark visited
for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== '#') {
dfs(nr, nc, next);
}
}
board[r][c] = ch; // restore (backtrack)
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
dfs(r, c, root); // start only matters if board[r][c] is a root edge
}
}
return found;
}word. Sharing prefixes is automatic — two words with the same start reuse the same early nodes.dfs entry — the prune. We immediately look up node.children.get(ch). If there is no such child, no word continues with this letter from here, so we return. This single check is the whole speedup.next.wordis non-null we've spelled a full word; push it and set next.word = null to avoid reporting duplicates, no Set required.#so the same cell isn't reused on this path, recurse into the four neighbors (in-bounds and not #), then write the original letter back — classic backtracking.dfs(r, c, root)for all cells; the root lookup cheaply rejects cells that don't begin any word.words). The search is O(m·n · 4·3L−1) where L is the longest word length — after the first move only 3 directions are new. Space is O(total characters) for the trie plus O(L) recursion depth.word when first collected; optionally prune now-empty trie leaves.# is O(1) extra space; a boolean matrix is clearer but costs O(m·n).| find MANY words in a grid | trie of words + one DFS |
| prefix can dead-end early | prune when child is absent |
| no cell reuse in a path | mark "#" then restore |
| avoid duplicate hits | store word at node, null it on find |
// trie: node = { children: Map, word: string|null }
function dfs(r, c, node) {
const ch = board[r][c];
const next = node.children.get(ch);
if (!next) return; // prune
if (next.word) { found.push(next.word); next.word = null; } // collect + de-dupe
board[r][c] = '#'; // visit
for (const [nr, nc] of neighbors) // 4-dir, in-bounds, not '#'
dfs(nr, nc, next);
board[r][c] = ch; // backtrack
}
for each cell (r,c) dfs(r, c, root);