Given an m×n 2D grid of characters and word as a string, we need to determine if the word can be constructed from letters of sequentially adjacent cells. The cells are considered sequentially adjacent when they are neighbors to each other either horizontally or vertically. The function should return TRUE if the word can be constructed and FALSE …

word-search.js

export function wordSearch(grid, word) {
  for (let row = 0; row < grid.length; ++row) {
    for (let col = 0; col < grid[row].length; ++col) {
      const result = wordSearchRec(grid, word, row, col, 0);
      if (result) {
        return true;
      }
    }
  }
  return false;
}

export function wordSearchRec(grid, word, row, col, index) {
  if (index === word.length) {
    return true;
  }

  if (!grid[row] || !grid[row][col] || grid[row][col] !== word[index]) {
    return false;
  }

  const char = grid[row][col];

  // mark the cell as visited
  grid[row][col] = "*";

  const result =
    wordSearchRec(grid, word, row + 1, col, index + 1) ||
    wordSearchRec(grid, word, row - 1, col, index + 1) ||
    wordSearchRec(grid, word, row, col + 1, index + 1) ||
    wordSearchRec(grid, word, row, col - 1, index + 1);

  // unmark the cell as visited for future iterations
  grid[row][col] = char;

  return result;
}

// wordSearchRec runs n * m times (dimensions of the board)
// depth of the recursion tree is l (length of the word)
// every recursive call spawns another 4 calls
// so finally it's O(n * m * 4^l)