7.3 Word Search (Grid Backtracking)

Demo: Word Search — LC 79 (Medium — Amazon/Google High)

Statement (Demo): Given an m × n board and a string word, return whether the word can be built from sequentially adjacent cells (horizontal or vertical). A cell may be used at most once. Example: board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word="ABCCED" → true | ⚡ m,n ≤ 6, len(word) ≤ 15

Approach: DFS from every cell — when the character matches, temporarily mark the cell '#' (visited), explore four directions, and restore the original character on the way back (undo).

function exist(board, word) {
  const m = board.length,
    n = board[0].length;
  const dfs = (i, j, k) => {
    if (k === word.length) return true;
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== word[k])
      return false;
    board[i][j] = "#"; // mark visited
    const found =
      dfs(i + 1, j, k + 1) ||
      dfs(i - 1, j, k + 1) ||
      dfs(i, j + 1, k + 1) ||
      dfs(i, j - 1, k + 1);
    board[i][j] = word[k]; // undo
    return found;
  };
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++) if (dfs(i, j, 0)) return true;
  return false;
}

Complexity: Time O(m·n·4^L) (L = word length), Space O(L)