39. Word Search

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 (horizontally or vertically). The same cell may not be used more than once.

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

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

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

Problem Breakdown:

1. Try starting the search from every cell in the grid. If any starting position finds the word, return true.

• for i in range(len(board)):
      for j in range(len(board[0])):
          if backtrack(board, word, i, j, 0):
              return True
  return False

2. The backtracking function checks: are we out of bounds? Does the current cell match the current character in the word? Have we matched all characters?

• def backtrack(board, word, i, j, k):
      if k == len(word):
          return True
      if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[k]:
          return False

3. Mark the current cell as visited (temporarily modify it) to prevent revisiting during the current path.

•     temp = board[i][j]
      board[i][j] = '#'

4. Recursively explore all four directions. If any direction finds the rest of the word, return true. Otherwise, restore the cell and backtrack.

•     found = (backtrack(board, word, i+1, j, k+1) or
               backtrack(board, word, i-1, j, k+1) or
               backtrack(board, word, i, j+1, k+1) or
               backtrack(board, word, i, j-1, k+1))
      board[i][j] = temp
      return found

Summary:

Backtracking DFS from each cell. At each step, check bounds and character match. Mark cells as visited during exploration and restore them when backtracking. Try all four directions recursively.

Time and Space Complexity:

Time Complexity: O(m * n * 4^L) - for each cell, we may explore paths of length L with 4 directions.

Space Complexity: O(L) - recursion depth equals the word length.

Python Solution:

def exist(board, word):
    def backtrack(i, j, k):
        if k == len(word):
            return True
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[k]:
            return False
        temp = board[i][j]
        board[i][j] = '#'
        found = (backtrack(i+1, j, k+1) or backtrack(i-1, j, k+1) or
                 backtrack(i, j+1, k+1) or backtrack(i, j-1, k+1))
        board[i][j] = temp
        return found
    for i in range(len(board)):
        for j in range(len(board[0])):
            if backtrack(i, j, 0):
                return True
    return False

JavaScript Solution:

var exist = function(board, word) {
    const backtrack = (i, j, k) => {
        if (k === word.length) return true;
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] !== word[k]) return false;
        const temp = board[i][j];
        board[i][j] = '#';
        const found = 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 found;
    };
    for (let i = 0; i < board.length; i++)
        for (let j = 0; j < board[0].length; j++)
            if (backtrack(i, j, 0)) return true;
    return false;
};

Java Solution:

class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++)
                if (backtrack(board, word, i, j, 0)) return true;
        return false;
    }
    private boolean backtrack(char[][] board, String word, int i, int j, int k) {
        if (k == word.length()) return true;
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(k)) return false;
        char temp = board[i][j];
        board[i][j] = '#';
        boolean found = backtrack(board, word, i+1, j, k+1) || backtrack(board, word, i-1, j, k+1) ||
                        backtrack(board, word, i, j+1, k+1) || backtrack(board, word, i, j-1, k+1);
        board[i][j] = temp;
        return found;
    }
}