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

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

Example 2

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

Steps

1. Depth-First Search (DFS): The most efficient approach is to use Depth-First Search. We'll explore the board recursively, trying to find the word.

2. Base Cases:

   • If the word is empty, we've found it! Return true.
   • If we're out of bounds or the current character doesn't match the next character in the word, return false.

3. Recursive Step:

   • Mark the current cell as visited (to avoid cycles).
   • Recursively explore the four adjacent cells (up, down, left, right).
   • If any recursive call returns true, we've found the word; return true.
   • Unmark the cell (backtrack) before returning false.

4. Iteration: Iterate through each cell in the board as a starting point for the DFS.

Explanation

The DFS approach systematically explores all possible paths in the board. By marking cells as visited, we prevent revisiting the same cell in a path, ensuring that we only consider valid paths. Backtracking (unmarking the cell) is crucial to allow exploration of other paths from the same cell.

Code

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        rows = board.size();
        cols = board[0].size();
        
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

private:
    int rows, cols;
    bool dfs(vector<vector<char>>& board, string& word, int row, int col, int index) {
        if (index == word.length()) return true; // Base case: word found
        if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != word[index]) return false; // Base case: out of bounds or mismatch

        char temp = board[row][col];
        board[row][col] = '#'; // Mark as visited

        // Explore adjacent cells
        bool found = dfs(board, word, row + 1, col, index + 1) ||
                     dfs(board, word, row - 1, col, index + 1) ||
                     dfs(board, word, row, col + 1, index + 1) ||
                     dfs(board, word, row, col - 1, index + 1);

        board[row][col] = 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 recursive call stack (depth of recursion is at most L). The space used by the visited array (implicitly using '#' character) is O(M*N) but is constant if we don't use a separate visited matrix.