Word Search

You are given an m x n grid of characters, board, and a string, word. Return true if word exists in the grid.

Problem Statement

You are given an m x n grid of characters, board, and a string, word. Return true if word exists in the grid.

The word must be built from letters in sequentially adjacent cells, where "adjacent" means the cells are next to each other horizontally or vertically (not diagonally). The same cell cannot be used more than once within a single word.

Solution

We solve this using backtracking. We try starting the search from every cell in the grid, and from each starting cell, we try to build the word one letter at a time, moving to neighboring cells.

Steps

• We use a helper function, backtrack(i, j, k):
  • i and j are the current cell's row and column.
  • k is the index of the letter in word we're currently trying to match.
• Inside backtrack:
  • If k equals the length of word, it means we've successfully matched every letter. We return true.
  • If the current position is out of bounds, or the letter at this cell doesn't match the letter we need (word.charAt(k)), this path doesn't work. We return false.
  • Otherwise, we temporarily mark this cell as visited, by replacing its letter with a placeholder character ('\0'), so we don't reuse it later in the same search path.
  • We then try moving to all four directions (down, up, right, left), checking if any of them can successfully match the rest of the word.
  • After trying all directions, we restore the original letter in this cell (backtrack), so it can be reused in a different search path later.
  • We return whether any of the four directions led to a successful match.
• In the main function, we loop through every cell in the grid, and try starting the search from each one. If any starting point leads to a full match, we return true.
• If no starting point works, we return false.

Code

var exist = function (board, word) {
    let n = board.length;
    let m = board[0].length;

    function backtrack(i, j, k) {
        if (k === word.length) {
            return true;
        }

        if (i < 0 || i >= n || j < 0 || j >= m || board[i][j] !== word.charAt(k)) {
            return false;
        }

        let temp = board[i][j];

        board[i][j] = '\0';

        const result = backtrack(i + 1, j, k + 1)
            || backtrack(i - 1, j, k + 1)
            || backtrack(i, j + 1, k + 1)
            || backtrack(i, j - 1, k + 1);

        board[i][j] = temp;
        return result;
    }

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (backtrack(i, j, 0)) {
                return true;
            }
        }
    }

    return false;
};