LietCode
Word Search

Word Search

Abhi's photo
Abhi
·

3 min read

Explain the Problem

Given an m x n board and a word, find if the 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:

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

Output: true

Short, Easy-to-Remember Solution/Approach

To solve this problem, we can use a recursive backtracking approach:

  1. Recursive Function: We'll create a helper function that searches for the word starting from each cell.

  2. Backtracking: If the current cell matches the current character in the word, we proceed to its neighbors. If we reach the end of the word, we return true.

Solution in JavaScript with Code Commenting

Here's the JavaScript solution with detailed comments:

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

  // Helper function for backtracking
  function backtrack(row, col, index) {
    // If we reach the end of the word, return true
    if (index === word.length) {
      return true;
    }

    // Check boundaries and if the current cell matches the current character in the word
    if (
      row < 0 || row >= rows ||
      col < 0 || col >= cols ||
      board[row][col] !== word[index]
    ) {
      return false;
    }

    // Mark the current cell as visited
    const temp = board[row][col];
    board[row][col] = '#';

    // Explore all four possible directions (up, down, left, right)
    const directions = [
      [0, 1],  // right
      [1, 0],  // down
      [0, -1], // left
      [-1, 0]  // up
    ];

    for (let [dx, dy] of directions) {
      if (backtrack(row + dx, col + dy, index + 1)) {
        return true;
      }
    }

    // Unmark the current cell
    board[row][col] = temp;

    return false;
  }

  // Start the search from each cell in the grid
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (backtrack(row, col, 0)) {
        return true;
      }
    }
  }

  return false;
}

Explanation of the Solution in Simple Terms

Imagine you have a word and a board filled with letters. You want to see if you can find the word on the board by moving from one letter to an adjacent one (up, down, left, right).

  • Recursive Function: This is like a helper that tries to find the word by starting from each letter on the board.

  • Backtracking: This means if the current path doesn't match the word, you go back and try a different path.

For each letter on the board, you check if it matches the first letter of the word. If it does, you continue to the next letter in the word by moving to an adjacent cell. If you reach the end of the word, you've found the word on the board. If not, you undo your last move and try another direction.

Code Explanation in Pointers

  1. Initialize Variables: Get the number of rows and columns in the board.

  2. Define Backtracking Function: Create a recursive function to explore different paths on the board.

  3. Base Case - Word Found: If the index equals the word length, return true.

  4. Boundary and Character Check: Check if the current cell is within boundaries and matches the current character in the word.

  5. Mark Cell as Visited: Temporarily mark the current cell as visited to avoid revisiting.

  6. Explore Directions: Try moving in all four possible directions (up, down, left, right).

  7. Unmark Cell: Restore the current cell's original value after exploring.

  8. Start Search: Start the search from each cell in the grid.

Complexity Analysis

  • Time Complexity: O(N * 3^L), where N is the number of cells in the board and L is the length of the word. Each cell can be visited at most once, and for each cell, we have three possible directions to explore (excluding the direction we came from).

  • Space Complexity: O(L), due to the recursion stack.

backtracking