Overview

Given an m × n board of characters and a list of words, return all words that can be formed on the board.

Each word must be constructed from letters of sequentially adjacent cells (horizontally or vertically). A cell cannot be reused within a single word, but can be reused across different words.

Implement findWords(board, words).

Constraints

• board is a 2D array of lowercase letters.
• words is an array of lowercase strings.
• Same cell cannot be used twice in one word path.
• Return words in any order, with no duplicates.
• Naive approach (run word-search per word) is too slow — use a Trie for $O(m \times n \times 4^L)$ total instead of $O(W \times m \times n \times 4^L)$.

Examples

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

findWords(board, ["oath","pea","eat","rain"]);
// → ["eat", "oath"]  (any order)

findWords([["a","b"],["c","d"]], ["abcb"]);
// → []  — can't reuse cells

Notes

• Trie + backtracking: Build a Trie from the word list. Then DFS from every cell, walking the Trie in parallel. When you reach a Trie node that marks a complete word, record it.
• Prune Trie nodes after finding a word to avoid duplicate results and speed up future searches.
• This is significantly faster than running the single-word search for each word independently.

Solution

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

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

  function dfs(r, c, node) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    const ch = board[r][c];
    if (ch === "#" || !node[ch]) return;

    const next = node[ch];
    if (next.word) {
      result.push(next.word);
      delete next.word; // avoid duplicates
    }

    board[r][c] = "#";
    dfs(r + 1, c, next);
    dfs(r - 1, c, next);
    dfs(r, c + 1, next);
    dfs(r, c - 1, next);
    board[r][c] = ch;
  }

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

  return result;
}

Resources

• Word Search II — LeetCode
• Trie — Wikipedia