079. Word Search

At a Glance

• Topic: Array
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 079

Problem Statement

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

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

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

Example 2:

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

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = &quot...

Approach & Solution Steps

• BFS per start — harder for full word (path state explosion).
• Optimal — DFS from each cell matching prefix — O(n * m * 4^L) worst.

Optimal JS Solution

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

  function dfs(row, col, position) {
    if (position === word.length) {
      return true;
    }
    if (row < 0 || col < 0 || row >= rows || col >= cols) {
      return false;
    }
    if (board[row][col] !== word[position]) {
      return false;
    }
    const temp = board[row][col];
    board[row][col] = '#';
    const found =
      dfs(row + 1, col, position + 1) ||
      dfs(row - 1, col, position + 1) ||
      dfs(row, col + 1, position + 1) ||
      dfs(row, col - 1, position + 1);
    board[row][col] = temp;
    return found;
  }

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

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.