Word Search

Examples

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Starting at the top-left A, you can trace A -> B -> C -> C -> E -> D moving through adjacent cells without reusing any of them.

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Starting from the S in the middle row, you can trace S -> E -> E down the right side of the grid.

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Tracing A -> B -> C reaches a C, but the only B adjacent to that C is the one already used at the start - and a cell can't be reused.

Constraints

• 1 <= board.length, board[i].length <= 6

• 1 <= word.length <= 15

• board and word consist only of English letters.

Approach

Since the word could start at any position on the grid, try every cell as a possible starting point. From a starting cell that matches the word's first letter, look at its neighbors for one that matches the second letter, then from there look for the third letter among its neighbors, and so on.

Along the way, you need to remember which cells are already part of the path so far, so the search never reuses one. If a path runs into a dead end - no unused neighbor matches the next letter needed - back up: un-mark the most recently used cell as available again, and try a different neighbor from the step before. That backing-up step is exactly what makes this backtracking: you commit to a cell, explore everything that follows, and undo the commitment the moment it stops paying off.

One way to track "already used" is a separate grid of true/false flags. A slightly leaner way skips the extra grid entirely: temporarily overwrite a used cell's letter with a placeholder character while exploring from it, then restore the original letter once you back up out of that cell - since a placeholder can never match a real letter, it naturally blocks reuse without needing any extra memory.

Solutions

Backtracking — Separate Visited Grid

Try starting the search from every cell. At each step, if the current cell's letter matches the letter the word needs at this point, mark the cell visited and recursively check whether the rest of the word can be traced from one of its unvisited neighbors. If a neighbor doesn't pan out, un-mark the current cell before returning, so a different starting path can reuse it.

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));

  function search(row, col, index) {
    if (index === word.length) return true;
    if (
      row < 0 || row >= rows ||
      col < 0 || col >= cols ||
      visited[row][col] ||
      board[row][col] !== word[index]
    ) {
      return false;
    }

    visited[row][col] = true;

    const found =
      search(row + 1, col, index + 1) ||
      search(row - 1, col, index + 1) ||
      search(row, col + 1, index + 1) ||
      search(row, col - 1, index + 1);

    visited[row][col] = false; // undo, whether or not it worked out

    return found;
  }

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (search(row, col, 0)) return true;
    }
  }

  return false;
}

Time: O(rows * cols * 4^L), where L is the word's length · Space: O(rows * cols) for the visited grid, plus O(L) recursion depth

Optimal — Mark In-Place Instead of a Visited Grid

Skip the separate visited grid. Instead, temporarily overwrite a cell's letter with a sentinel character (one that can never appear in the word) while exploring from it, then restore the original letter afterward. This saves the extra rows x cols grid, at the cost of briefly mutating the board during the search.

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

  function search(row, col, index) {
    if (index === word.length) return true;
    if (
      row < 0 || row >= rows ||
      col < 0 || col >= cols ||
      board[row][col] !== word[index]
    ) {
      return false;
    }

    const original = board[row][col];
    board[row][col] = "#"; // sentinel: can never match a real letter

    const found =
      search(row + 1, col, index + 1) ||
      search(row - 1, col, index + 1) ||
      search(row, col + 1, index + 1) ||
      search(row, col - 1, index + 1);

    board[row][col] = original; // restore before returning

    return found;
  }

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (search(row, col, 0)) return true;
    }
  }

  return false;
}

Time: O(rows * cols * 4^L) · Space: O(L) recursion depth only - no visited grid, since the board itself is restored after use