Problem Statement

You are given a 2D grid of characters board of dimensions n x m, and a string word. You need to determine if word can be formed by a sequence of adjacent cells in board.

• A cell in the grid is "adjacent" to another if it is horizontally or vertically next to it.
• The same cell cannot be used more than once in a single sequence.
• Return true if word exists in the grid, and false otherwise.

LeetCode

• https://leetcode.com/problems/word-search/description/

Constraints

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.

Examples

Example 1:

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

Output = true

Explanation:
The word "ABCCED" can be traced as follows: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (2,1).

Example 2:

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

Output = true

Explanation:
The word "SEE" can be formed by navigating as follows:

Start from (1,3) → "S"
Move to (2,3) → "E"
Move to (2,2) → "E"
This path successfully forms the word "SEE" without revisiting any cells.

Example 3:

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

Output = false

Explanation:
The word "ABCB" cannot be formed as:

While we can match "A" at (0,0), "B" at (0,1), and "C" at (0,2),
The next "B" would require revisiting the cell at (0,1), which is not allowed.
Thus, it is impossible to construct the word "ABCB" with unique cells in this grid.

Different Approaches

1️⃣ DFS with Backtracking

Intuition:

The problem can be solved by traversing the grid and performing a depth-first search (DFS) for each possible starting position. At each cell, we check if the current character matches the corresponding character of the word. If it does, we explore all four directions (up, down, left, right) recursively until we find the complete word or exhaust all possibilities.

Approach

1. Implement a recursive function backtrack that takes the current position (i, j) in the grid and the current index k of the word.
2. Base cases:
   • If k equals the length of the word, return True, indicating that the word has been found.
   • If the current position (i, j) is out of the grid boundaries or the character at (i, j) does not match the character at index k of the word, return False.
3. Mark the current cell as visited by changing its value or marking it as empty.
4. Recursively explore all four directions (up, down, left, right) by calling backtrack with updated positions (i+1, j), (i-1, j), (i, j+1), and (i, j-1).
5. If any recursive call returns True, indicating that the word has been found, return True.
6. If none of the recursive calls returns True, reset the current cell to its original value and return False.
7. Iterate through all cells in the grid and call the backtrack function for each cell. If any call returns True, return True, indicating that the word exists in the grid. Otherwise, return False.

Code:

class Solution {
public:
    
    // Helper function to check if the word is present starting from the given cell
    bool isWordPresent(int currentRow, int currentCol, int currentIndex, vector<vector<char>>& board, string &word) {
        // Base case: If we have matched all characters in the word, return true
        if (currentIndex == word.size()) return true;
        
        // Boundary and mismatch check:
        // If the current cell is out of bounds, or the character does not match the current character in the word, return false
        if (currentRow < 0 || currentCol < 0 || currentRow >= board.size() || currentCol >= board[0].size() ||
            board[currentRow][currentCol] != word[currentIndex])
            return false;
        
        // Mark the cell as visited by setting it to a special character (e.g., '.')
        // This helps to avoid revisiting the same cell in the current search path
        board[currentRow][currentCol] = '.';
        
        // Recursively explore all four directions: Left, Right, Up, Down
        // If any direction completes the word, return true
        bool ans = isWordPresent(currentRow, currentCol - 1, currentIndex + 1, board, word) // Left
                || isWordPresent(currentRow, currentCol + 1, currentIndex + 1, board, word) // Right
                || isWordPresent(currentRow - 1, currentCol, currentIndex + 1, board, word) // Up
                || isWordPresent(currentRow + 1, currentCol, currentIndex + 1, board, word); // Down
        
        // Restore the cell's original value after exploring all directions (backtracking step)
        board[currentRow][currentCol] = word[currentIndex];
        
        return ans; // Return true if the word is found, otherwise false
    }
    
    // Main function to determine if the word exists in the grid
    bool exist(vector<vector<char>>& board, string word) {
        int totalRows = board.size(); // Total number of rows in the grid
        int totalCols = board[0].size(); // Total number of columns in the grid
        
        // Loop through each cell in the grid
        for (int currentRow = 0; currentRow < totalRows; currentRow++) {
            for (int currentCol = 0; currentCol < totalCols; currentCol++) {
                // If the current cell matches the first character of the word
                if (board[currentRow][currentCol] == word[0]) {
                    // Start a DFS search from this cell to find the word
                    if (isWordPresent(currentRow, currentCol, 0, board, word))
                        return true; // If the word is found, return true
                }
            }
        }
        
        return false; // If no path forms the word, return false
    }
};

/*
Time and Space Complexity Analysis:
- Let m be the number of rows and n be the number of columns in the grid.
- Let k be the total cells in the grid (m * n).

Time Complexity: O((m * n) * 4^(word.length()))
- For each cell in the grid (m * n), a DFS search is initiated.
- Each DFS explores up to 4 directions recursively, leading to an exponential time complexity with respect to the length of the word.

Space Complexity: O(word.length())
- The recursion stack depth depends on the length of the word, making it O(word.length()) for the backtracking process.
*/

OR

class Solution {
public:
    // Helper function to search for the word in all four directions
    bool search(vector<vector<char>>& board, int i, int j, int k, int m, int n, string& word) {
        // Base case: If we have found all characters
        if (k == word.length()) {
            return true;
        }

        // Boundary conditions and mismatched character check
        if (i < 0 || j < 0 || i >= n || j >= m || board[i][j] != word[k] || board[i][j] == '.') {
            return false;
        }

        // Mark the cell as visited by setting it to a placeholder character
        char temp = board[i][j];
        board[i][j] = '.';

        // Initialize status as false
        bool status = false;

        // Explore all four directions: right, left, up, down
        status = search(board, i, j + 1, k + 1, m, n, word) ||  // right
                 search(board, i, j - 1, k + 1, m, n, word) ||  // left
                 search(board, i - 1, j, k + 1, m, n, word) ||  // up
                 search(board, i + 1, j, k + 1, m, n, word);    // down

        // Restore the original value of the cell (backtracking step)
        board[i][j] = temp;
        
        return status;
    }

    bool exist(vector<vector<char>>& board, string word) {
        int m = board[0].size(); // Number of columns
        int n = board.size();    // Number of rows

        // Loop through each cell as a potential starting point
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // If the first character matches, start the search
                if (board[i][j] == word[0] && search(board, i, j, 0, m, n, word)) {
                    return true; // Word found
                }
            }
        }
        return false; // Word not found
    }
};

OR:

class Solution {
public:
    // Arrays to move in 4 directions: up, right, down, left
    int dimX[4] = {-1, 0, 1, 0};  
    int dimY[4] = {0, 1, 0, -1};

    // Recursive DFS function to search the word
    bool dfs(vector<vector<char>>& board, string& word, int idx, int row, int col, vector<vector<bool>>& vis) {
        // ✅ Base case: if the current index matches the word length, we’ve matched all characters
        if (idx == word.length()) return true;

        int n = board.size(), m = board[0].size();

        // 🔒 Boundary checks and pruning:
        // - Out of bounds
        // - Already visited cell
        // - Current cell does not match the character in word at position `idx`
        if (row < 0 || row >= n || col < 0 || col >= m || vis[row][col] || board[row][col] != word[idx])
            return false;

        // 🔒 Mark the current cell as visited
        vis[row][col] = true;

        // 🔁 Explore all 4 directions (up, right, down, left)
        for (int d = 0; d < 4; ++d) {
            int newRow = row + dimX[d];
            int newCol = col + dimY[d];
            // 🧭 If any path from here leads to a full match, return true
            if (dfs(board, word, idx + 1, newRow, newCol, vis))
                return true;
        }

        // 🔙 Backtrack: Unmark the current cell for other paths
        vis[row][col] = false;

        // ❌ If no path leads to a solution from this cell, return false
        return false;
    }

    // Main function to check if the word exists in the board
    bool exist(vector<vector<char>>& board, string word) {
        int n = board.size();
        int m = board[0].size();

        // 🧵 Try starting DFS from each cell
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                // Create a fresh visited matrix for each starting cell
                vector<vector<bool>> vis(n, vector<bool>(m, false));
                // If starting from (i, j) leads to a match, return true
                if (dfs(board, word, 0, i, j, vis))
                    return true;
            }
        }

        // ❌ If no path found from any starting cell, return false
        return false;
    }
};

Complexity Analysis:

• Time Complexity:
  • Outer Loops in exist function
    • We loop through every cell in the board to find possible starting points for the word, resulting in a total of O(m * n) iterations, where m is the number of rows and n is the number of columns.
  • Recursive Calls in search function
    • For each starting point, we initiate a recursive search that explores all four directions: right, left, up, and down.
    • In the worst case, the recursion visits every cell in the board and explores all four directions from each cell.
    • This results in an exponential time complexity of O(4^k), where k is the length of the word.
    • However, due to backtracking and boundary conditions (cells already visited or out of bounds), not all paths are fully explored. Still, the worst case remains O(4^k) for certain configurations of the board and word.
  • Overall Time Complexity:

    • Combining the outer loop and the recursive exploration, the worst-case time complexity is:

      O(m * n * 4^k) 

    • This worst case happens if each character of the word can potentially match every cell in the board, causing maximum recursive exploration.
• Space Complexity:
  • Recursive Stack:
    • The recursive function search has a maximum depth of recursion equal to the length of word, since each recursive call progresses by one character.
    • Therefore, the space complexity due to recursion is O(k), where k is the length of word.
  • In-Place Modifications:
    • The board is modified in place by marking cells as visited (setting them to '.'), which does not require additional memory for marking.
    • However, this does not affect the asymptotic space complexity, as no additional space is allocated.
  • Overall Space Complexity:
    • The space complexity is dominated by the recursive stack, which is O(k).