Word Search medium

Problem Statement

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 cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

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

Example 2:

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

Steps and Explanation

The problem can be solved using Depth-First Search (DFS). We'll iterate through each cell in the board. If we find a cell that matches the first letter of the word, we'll initiate a DFS search from that cell.

The DFS function will recursively explore adjacent cells, checking if the next letter in the word matches the current cell's letter. To avoid revisiting cells, we'll mark the current cell as visited. If we reach the end of the word, we've found it. If we reach a dead end (no matching adjacent cell or we've hit a boundary), we backtrack and try a different path.

Algorithm:

1. Iterate through the board: For each cell, check if it matches the first letter of the word.
2. DFS (recursive function):
   • Base Cases:
     • If the word is empty, return true (word found).
     • If the current cell is out of bounds, or the cell's letter doesn't match the current letter in the word, or the cell is already visited, return false.
   • Recursive Step:
     • Mark the current cell as visited.
     • Recursively call DFS for adjacent cells (up, down, left, right).
     • Unmark the current cell (backtrack).
3. Return false if the DFS doesn't find the word.

Code (C#)

public class Solution {
    public bool Exist(char[][] board, string word) {
        int m = board.Length;
        int n = board[0].Length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (DFS(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private bool DFS(char[][] board, string word, int i, int j, int k) {
        int m = board.Length;
        int n = board[0].Length;

        // Base cases
        if (k == word.Length) return true; // Word found
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k]) return false; // Out of bounds or mismatch

        char temp = board[i][j];
        board[i][j] = '#'; // Mark as visited

        // Explore adjacent cells
        bool found = DFS(board, word, i + 1, j, k + 1) ||
                     DFS(board, word, i - 1, j, k + 1) ||
                     DFS(board, word, i, j + 1, k + 1) ||
                     DFS(board, word, i, j - 1, k + 1);

        board[i][j] = temp; // Backtrack: unmark the cell

        return found;
    }
}

Complexity

• Time Complexity: O(M * N * 4^L), where M and N are the dimensions of the board, and L is the length of the word. In the worst case, we might explore all possible paths.
• Space Complexity: O(L) due to the recursion depth (call stack) for DFS. In addition, we use O(MN) space for the board itself. Therefore overall space complexity is O(MN + L) which simplifies to O(M*N) for large boards.