Patterns

Build a trie of words; query with prefix or backtracking traversal

When to useWord search II, autocomplete, longest common prefix, dictionary lookup

recursive

Autocomplete

autocomplete

Prefix Count

prefix_count

Word Search II | Depth First Search + Trie

word_search_ii

Design Add And Search Wordsmedium

design_add_and_search_words · no slots

Implement Triemedium

implement_trie · no slots

BUILD TRIE

insert all words char-by-char into nested children map

const root = { children: {}, count: 0 };

const root = { children: {}, count: 0 };
for (const word of words) {
  let node = root;
  for (const ch of word) {
    if (!node.children[ch]) node.children[ch] = { children: {}, count: 0 };
    node = node.children[ch];
    node.count++;
  }
}

const root = {};
for (const word of words) {
  let node = root;
  for (const ch of word) {
    if (!node[ch]) node[ch] = {};
    node = node[ch];
  }
  node.word = word;
}

—

BASE CASE

if cell out of bounds OR no child for ch, return

if (!node.children[ch]) node.children[ch] = { children: {}, count: 0 };

if (!node.children[ch]) return 0;

const ch = board[r]?.[c];
if (!ch || !node[ch]) return;

—

[MATCH]

if trie node marks end-of-word, record match (and clear to dedupe)

if (!unique && node.count === 1) { strokes = i + 1; unique = true; }

return node.count;

if (next.word) { result.push(next.word); next.word = null; }

—

RECURSE

DFS in 4 directions (or descend the trie further)

node = node.children[ch]; node.count++;

node = node.children[ch];

dfs(r + 1, c, next);
dfs(r - 1, c, next);
dfs(r, c + 1, next);
dfs(r, c - 1, next);

—

prune

if trie subtree empty, can drop; backtrack mark on cell

if (!unique) strokes = word.length;

(no-op — missing child is already handled by base case)

board[r][c] = '#';  // before
board[r][c] = ch;   // after (backtrack)

—

RETURN

return matched results

return total;

return prefixes.map((prefix) => ... );

return words.filter((w) => found.has(w));

—