Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Trie

Guide 3 of 6 · Path 3 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

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 only
Time 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