Word Search

You are given a two-dimensional mat[][] of size n*m containing English alphabets and a string word. Check if the word exists on the mat. The word can be constructed by using letters from adjacent cells, either horizontally or vertically. The same cell cannot be used more than once.

Examples :

Input: mat[][] = [['T', 'E', 'E'], ['S', 'G', 'K'], ['T', 'E', 'L']], word = "GEEK"
Output: true
Explanation:

The letter cells which are used to construct the "GEEK" are colored.

Input: mat[][] = [['T', 'E', 'U'], ['S', 'G', 'K'], ['T', 'E', 'L']], word = "GEEK"
Output: false
Explanation:

It is impossible to construct the string word from the mat using each cell only once.

Input: mat[][] = [['A', 'B', 'A'], ['B', 'A', 'B']], word = "AB"
Output: true
Explanation:

There are multiple ways to construct the word "AB".

Constraints:
1 ≤ n, m ≤ 6
1 ≤ L ≤ 15
mat and word consists of only lowercase and uppercase English letters.

Approach 01

class Solution {
public:
    bool isWordExist(vector<vector<char>>& grid, string& word) {
        int rows = grid.size();
        int cols = grid[0].size();

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] == word[0]) {
                    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
                    if (dfs(grid, row, col, 0, word, visited)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

private:
    bool dfs(vector<vector<char>>& grid, int row, int col, int index, string& word, vector<vector<bool>>& visited) {
        if (index == word.size()) {
            return true;
        }

        // Base case: Out of bounds, already visited, or character mismatch
        if (row < 0 || col < 0 || row >= grid.size() || col >= grid[0].size() || visited[row][col] || grid[row][col] != word[index]) {
            return false;
        }

        visited[row][col] = true;

        // Explore all four directions: left, right, up, down
        if (dfs(grid, row, col - 1, index + 1, word, visited) ||  // Left
            dfs(grid, row, col + 1, index + 1, word, visited) ||  // Right
            dfs(grid, row - 1, col, index + 1, word, visited) ||  // Up
            dfs(grid, row + 1, col, index + 1, word, visited)) {  // Down
            return true;
        }

        visited[row][col] = false;
        return false;
    }
};

class Solution:
    def isWordExist(self, grid: list[list[str]], word: str) -> bool:
        rows = len(grid)
        cols = len(grid[0])

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == word[0]:
                    visited = [[False] * cols for _ in range(rows)]
                    if self.dfs(grid, row, col, 0, word, visited):
                        return True
        return False

    def dfs(self, grid: list[list[str]], row: int, col: int, index: int, word: str, visited: list[list[bool]]) -> bool:
        if index == len(word):
            return True

        # Base case: Out of bounds, already visited, or character mismatch
        if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]) or visited[row][col] or grid[row][col] != word[index]:
            return False

        visited[row][col] = True

        # Explore all four directions: left, right, up, down
        if (self.dfs(grid, row, col - 1, index + 1, word, visited) or  # Left
            self.dfs(grid, row, col + 1, index + 1, word, visited) or  # Right
            self.dfs(grid, row - 1, col, index + 1, word, visited) or  # Up
            self.dfs(grid, row + 1, col, index + 1, word, visited)):   # Down
            return True

        visited[row][col] = False
        return False

Time Complexity:

• Grid Traversal:

  We iterate through all cells in the grid, taking \( O(R \times C) \) time, where \( R \) is the number of rows and \( C \) is the number of columns.

• Depth-First Search (DFS):

  In the worst case, each DFS call explores four possible directions, leading to an exponential growth of \( O(4^L) \), where \( L \) is the length of the word.

• Overall Time Complexity:

  \( O(R \times C \times 4^L) \).

Space Complexity:

• Visited Matrix:

  We use an additional \( R \times C \) matrix to keep track of visited cells, contributing \( O(R \times C) \) space.

• Recursive Call Stack:

  The depth of the recursion can go up to \( L \), leading to a worst-case space complexity of \( O(L) \) due to recursive calls.

• Overall Space Complexity:

  \( O(R \times C + L) \), which simplifies to \( O(R \times C) \) in the worst case.