Typorithm · hard

Word Search II

word-search-iitriestrie-dfsbacktrackinggrid

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Word Search II

Tries

Index words in a trie, then DFS the grid following trie edges, collecting words at end-nodes and backtracking on visited cells.

Searching each word separately is wasteful; one trie lets a single grid DFS match all words at once.

From each cell, descend the trie only while letters match, pruning dead branches immediately.

Mark cells visited during recursion and restore them after, collecting words at isEnd nodes and unflagging to dedupe.

One trie for all words.

DFS follows trie edges, prunes early.

Mark/restore cells; unflag found words.

function findWords(board, words) {
  const root = new Trie();
  for (const word of words) {
    root.insert(word);
  }

  const result = [];
  const rows = board.length;
  const cols = board[0].length;

  function dfs(r, c, node, path) {
    if (r < 0 || c < 0 || r >= rows || c >= cols) {
      return;
    }
    const ch = board[r][c];
    if (ch === "#" || !node.children.has(ch)) {
      return;
    }
    const next = node.children.get(ch);
    const word = path + ch;
    if (next.isEnd) {
      result.push(word);
      next.isEnd = false;
    }
    board[r][c] = "#";
    dfs(r + 1, c, next, word);
    dfs(r - 1, c, next, word);
    dfs(r, c + 1, next, word);
    dfs(r, c - 1, next, word);
    board[r][c] = ch;
  }

  for (let r = 0; r < rows; r += 1) {
    for (let c = 0; c < cols; c += 1) {
      dfs(r, c, root, "");
    }
  }

  return result;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Trie of words

Index all target words in one trie to prune the search.

root.insert(word)

2. Prune dead paths

Stop when the cell is visited or no trie edge matches.

if (ch === "#" || !node.children.has(ch)) {

3. Collect + dedupe

Record a found word and unflag it to avoid duplicates.

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

4. Mark visited

Temporarily block the cell, then restore it after recursing.

board[r][c] = "#";

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.