Word Search on a Board

Use a trie loaded with target words to prune the backtracking search on a 2D character board so that paths not matching any prefix are abandoned before they are fully explored.

6 min read Level 4/5 #dsa#trie#backtracking

What you'll learn

Load a word list into a trie and use it to guide board DFS
Implement backtracking with visited marking on a 2D grid
Explain why prefix pruning reduces the search space compared to brute force

The classic word-search problem: given a 2D board of characters and a list of target words, find all words that can be formed by walking adjacent cells (up/down/left/right) without reusing a cell in the same path.

The naive approach is a separate DFS for every word — O(W · R · C · 4^L) where W is the word count, R and C are the board dimensions, and L is the word length. Loaded into a trie first, all words share a single DFS over the board: any path that does not match a stored prefix is abandoned immediately.

Building the Trie

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
    this.word = null; // store the complete word here for easy collection
  }
}

function buildTrie(words) {
  const root = new TrieNode();
  for (const word of words) {
    let node = root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }
    node.isEnd = true;
    node.word = word;
  }
  return root;
}

Storing the full word on the terminal node avoids reconstructing it from the path during collection.

Board DFS with Trie Pruning

function findWords(board, words) {
  const rows = board.length;
  const cols = board[0].length;
  const root = buildTrie(words);
  const found = new Set();

  function dfs(r, c, node) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    const char = board[r][c];
    if (char === "#") return;           // already visited in this path
    if (!node.children.has(char)) return; // no word with this prefix

    const next = node.children.get(char);
    if (next.isEnd) found.add(next.word);

    board[r][c] = "#";                  // mark visited
    dfs(r - 1, c, next);
    dfs(r + 1, c, next);
    dfs(r, c - 1, next);
    dfs(r, c + 1, next);
    board[r][c] = char;                 // restore (backtrack)
  }

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

  return [...found];
}

Temporarily replacing a cell with "#" is an in-place visited marker that is automatically undone when the recursive call returns — the backtracking mechanism in one line.

Worked Example

const board = [
  ["o", "a", "a", "n"],
  ["e", "t", "a", "e"],
  ["i", "h", "k", "r"],
  ["i", "f", "l", "v"],
];

const words = ["oath", "pea", "eat", "rain", "oat"];

findWords(board, words);
// ["oath", "eat", "oat"]  (order may vary)

"pea" and "rain" are absent because the board cannot form those letter sequences in adjacent cells.

Why Pruning Helps

Approach	Time (approx.)	Notes
Brute force (one DFS per word)	O(W · R · C · 4^L)	redundant prefix checks
Trie + single DFS	O(R · C · 4^L)	shared prefix traversal
Trie + leaf pruning	Better in practice	delete terminal nodes after finding

An additional optimization: after collecting a word, set node.isEnd = false and remove childless nodes from their parent. This prevents finding the same word twice and shrinks the trie as the search progresses.

Up Next

Shift from searching a board to searching within a single string by encoding every suffix of that string into one trie structure.

Suffix Tries and Substring Queries →