Tries crash course ↗ · 149

212. Word Search II

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.

● HardTrieBacktrackingMatrix DFSTypeScript

PROBLEM What we're solving

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.

KEY IDEA One trie-guided DFS, not one DFS per word

Insight → if you search the board separately for each word, the same partial paths get re-explored over and over. Put all the words into a 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.

RECIPE Build the trie, then DFS + backtrack

  • 1 · Build a trie of every word. Store the full word string at its terminal node so a hit is self-describing — why: lets you collect without tracking the path.
  • 2 · DFS from each cell, carrying the current trie node. Look up node.children.get(board[r][c]). If it's missing, return — why: no dictionary word continues with this letter, so the branch is hopeless.
  • 3 · On a terminal node, record the word and null out its marker — why: de-dupes repeats without a separate Set.
  • 4 · Mark the cell visited (overwrite with #), recurse into the 4 neighbors, then restore it — why: backtracking frees the cell for other paths.
Classic confusion → the start cell doesmatter, but you don't need a special case: just call 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.

COST Complexity & alternatives

DFS once per word
O(W · m·n · 4ᴸ)
Re-walks shared prefixes for every word W.
Trie + single DFS
O(m·n · 4·3ᴸ⁻¹)
One walk; trie prunes dead branches early.

Why the trie wins

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.

Pattern transfer →"match many strings at once over a structure" is the trie-DFS signature: it powers Word Search (single word, no trie needed), Replace Words (shortest root), Concatenated Words, and Aho–Corasick multi-pattern matching.

RUN IT DFS the board along trie edges

step 0 / 45
STARTBuild a trie from oath, pea, eat, rain, then DFS every cell, following only letters that exist as trie edges.
1interface TrieNode {
2  children: Map<string, TrieNode>;
3  word: string | null;   // non-null only at the end of a word
4}
5 
6▶function findWords(board: string[][], words: string[]): string[] {
7▶  // 1. Build a trie of all target words.
8▶  const root: TrieNode = { children: new Map(), word: null };
9▶  for (const w of words) {
10    let node = root;
11    for (const ch of w) {
12      if (!node.children.has(ch)) {
13        node.children.set(ch, { children: new Map(), word: null });
14      }
15      node = node.children.get(ch)!;
16    }
17    node.word = w;             // mark terminal
18  }
19 
20▶  const rows = board.length;
21▶  const cols = board[0].length;
22▶  const found: string[] = [];
23 
24  function dfs(r: number, c: number, node: TrieNode): void {
25    const ch = board[r][c];
26    const next = node.children.get(ch);
27    if (!next) return;         // prune: no word continues here
28 
29    if (next.word !== null) {  // reached a complete word
30      found.push(next.word);
31      next.word = null;        // de-dupe without a Set
32    }
33 
34    board[r][c] = '#';         // mark visited
35    for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
36      const nr = r + dr, nc = c + dc;
37      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== '#') {
38        dfs(nr, nc, next);
39      }
40    }
41    board[r][c] = ch;          // restore (backtrack)
42  }
43 
44  for (let r = 0; r < rows; r++) {
45    for (let c = 0; c < cols; c++) {
46      dfs(r, c, root);         // start only matters if board[r][c] is a root edge
47    }
48  }
49  return found;
50}
path·empty
State
—
cell (r,c)
—
ch
root
node
—
next
—
board[r][c]
∅
prefix (path)
{ }
found
current cell / chpath tip / trie node / prefixpath so far / foundpruned / visited (#)
slowfast

TYPESCRIPT The solution, annotated

findWords.ts
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;
}

Reading it block by block

Build the trie. Each word is inserted character by character; the terminal node stores the whole word in 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.
Collect on a terminal. If next.wordis non-null we've spelled a full word; push it and set next.word = null to avoid reporting duplicates, no Set required.
Visit, recurse, restore. Overwrite the cell with #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.
Launch from every cell. Calling dfs(r, c, root)for all cells; the root lookup cheaply rejects cells that don't begin any word.
Complexity → Building the trie is O(total characters in 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.

INTERVIEWFollow-ups they'll ask

  • "How do you avoid duplicate results?" Null the terminal word when first collected; optionally prune now-empty trie leaves.
  • "Why a trie instead of a hash set of words?" The trie lets you prune on prefixes mid-DFS; a hash set only tells you about complete words.
  • "In-place visited marker vs a visited matrix?" Overwriting with # is O(1) extra space; a boolean matrix is clearer but costs O(m·n).
  • "What if a word can reuse cells?"Drop the visited marker — but then paths can be infinite, so you'd need a different bound (e.g. word length).
  • "Thousands of words?" Prune the trie aggressively after finds; the search cost stays tied to the grid and longest word, not the word count.

OPTIMAL Trie

findWords.ts
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;
}
Complexity → Building the trie is O(total characters in 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.

ALT 1 Per-word DFS (Word Search I, repeated)

O(W · m·n · 4ᴸ) time · O(L) space

For every word you re-launch a fresh backtracking search from each matching cell, so two words sharing a prefix like eat and eats re-walk that prefix from scratch — the redundant work the trie collapses by descending all words in one traversal.

approach-2.ts
function findWords(board: string[][], words: string[]): string[] {
  const rows = board.length;
  const cols = board[0].length;
  const found = new Set<string>();   // de-dupe identical words / multiple matches

  // Try to trace word[i..] starting at cell (r, c).
  function dfs(r: number, c: number, word: string, i: number): boolean {
    if (i === word.length) return true;        // whole word matched
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[i]) return false; // letter mismatch (also blocks visited '#')

    const ch = board[r][c];
    board[r][c] = '#';                          // mark visited — no reuse on this path
    const ok =
      dfs(r - 1, c, word, i + 1) ||
      dfs(r + 1, c, word, i + 1) ||
      dfs(r, c - 1, word, i + 1) ||
      dfs(r, c + 1, word, i + 1);
    board[r][c] = ch;                           // restore (backtrack)
    return ok;
  }

  for (const word of words) {
    if (word.length === 0 || found.has(word)) continue;
    let hit = false;
    for (let r = 0; r < rows && !hit; r++) {
      for (let c = 0; c < cols && !hit; c++) {
        if (board[r][c] === word[0] && dfs(r, c, word, 0)) {
          found.add(word);
          hit = true;                           // this word is found; move to next word
        }
      }
    }
  }

  return [...found];
}
Note → Identical to running Word Search Ionce per word. It's the natural first solution and easy to get right, but with W words and longest length L it costs O(W · m·n · 4ᴸ) — the word count multiplies the whole board search. The trie removes that W factor by matching every word during a single DFS and pruning a branch the instant no word continues.

MNEMONIC The one-liner

"Trie the words, walk the grid; child missing → quit; word here → grab it; mark, roam, restore."

TRIGGERS When you see ___ → reach for ___

find MANY words in a gridtrie of words + one DFS
prefix can dead-end earlyprune when child is absent
no cell reuse in a pathmark "#" then restore
avoid duplicate hitsstore word at node, null it on find

SKELETON The reusable shape

skeleton.ts
// 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);

FLASHCARDS Tap to flip

Core data structure for Word Search II?
A trieof all the words, DFS'd in lockstep with the board so one traversal matches every word.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
Why use a trie instead of running DFS once per word?
QUESTION 02
During DFS, you prune (return early) exactly when:
QUESTION 03
How do you signal that a trie node ends a word, and avoid duplicate results?
QUESTION 04
How is "no cell reused within one word" enforced?
QUESTION 05
For board=[oaan;etae;ihkr;iflv], words=[oath,pea,eat,rain], the result is:
QUESTION 06
Search-time complexity (L = longest word length)?
QUESTION 07
A common further optimization once a word is found is to:
QUESTION 08
#212 · Word Search IIFind every dictionary word spellable along adjacent cells of a grid. Build a trie of all words and run one backtracking DFS that follows board letters and trie edges together, pruning dead prefixes immediately.Which algorithmic approach does this primarily use?
QUESTION 09
#212 · Word Search IIFind every dictionary word spellable along adjacent cells of a grid. Build a trie of all words and run one backtracking DFS that follows board letters and trie edges together, pruning dead prefixes immediately.Which implementation correctly solves it?