Overview

Given an m × n grid of characters and a string word, return true if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically). Each cell may be used only once per word.

Implement wordExists(board, word).

Constraints

• board is a 2D array of single characters.
• word is a non-empty string.
• Same cell cannot be reused within a single path.
• Cells are adjacent horizontally or vertically (not diagonally).
• Aim for $O(m \times n \times 4^L)$ where L is the word length (backtracking with pruning).

Examples

const board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
];

wordExists(board, "ABCCED");  // true
wordExists(board, "SEE");     // true
wordExists(board, "ABCB");    // false — can't reuse B

Notes

• DFS/backtracking from every cell that matches the first character.
• Mark cells as visited during recursion (e.g. replace with #), restore on backtrack.
• Prune early: if the current character doesn't match, return immediately.
• No need for a separate visited set if you temporarily mutate the board.

Solution

function wordExists(board, word) {
  const rows = board.length, cols = board[0].length;

  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[idx]) return false;

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

    const found = dfs(r + 1, c, idx + 1) || dfs(r - 1, c, idx + 1) ||
                  dfs(r, c + 1, idx + 1) || dfs(r, c - 1, idx + 1);

    board[r][c] = saved;
    return found;
  }

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

  return false;
}

Resources

• Word Search — LeetCode
• Backtracking — Wikipedia