✅ EASY TO UNDERSTAND ☑️
PLEASE UPVOTE MY SOLUTION IF YOU LIKE IT\n# CONNECT WITH ME\n### https://www.linkedin.com/in/pratay-nandy-9ba57b229/\n#### https://www.instagram.com/pratay_nand
# **PLEASE UPVOTE MY SOLUTION IF YOU LIKE IT**\n# **CONNECT WITH ME**\n### **[https://www.linkedin.com/in/pratay-nandy-9ba57b229/]()**\n#### **[https://www.instagram.com/_pratay_nandy_/]()**\n\n# Approach\n\n\nExplanation:\n\n1. **`search` function:**\n    - The recursive `search` function explores the board to find a match for the given word starting from the current position `(i, j)`.\n    - It returns `true` if the entire word is found, and `false` otherwise.\n    - The function explores neighbors in all four directions (up, down, left, right) if the current cell matches the current character of the word.\n\n2. **`exist` function:**\n    - The `exist` function iterates over each cell in the board and checks if the word can be formed starting from that cell using the `search` function.\n    - It returns `true` if any match is found, indicating that the word exists on the board. Otherwise, it returns `false`.\n\n3. **Marking Visited Cells:**\n    - The function marks visited cells with the character `\'#\'` to avoid revisiting the same cell in the recursive exploration.\n\n4. **Backtracking:**\n    - Before returning from the `search` function, the original character of the current cell is restored, allowing backtracking.\n\nOverall, the code uses a backtracking approach to explore all possible paths on the board to find a match for the given word. The time complexity depends on the number of cells in the board and the length of the word. In the worst case, it is O(N * M * 4^k), where N and M are the dimensions of the board, and k is the length of the word.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:**0(N * M * 4^k)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:**0(1)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n![upvote2.png](https://assets.leetcode.com/users/images/6198d926-527c-42f7-a663-aaf8d62ed44c_1704980133.0159707.png)\n\n\n# Code\n```cpp\nclass Solution {\npublic:\n    bool search(int i, int j, int n, int m, vector<vector<char>>& board, int k, string word) {\n        if (k == word.size()) return true;  // If we have matched all characters in the word, return true\n        if (i == n || i < 0 || j < 0 || j == m || board[i][j] != word[k]) {\n            return false;  // If current cell is out of bounds or does not match the current character in word, return false\n        }\n        \n        char ch = board[i][j];  // Store the current character before exploring neighbors\n        board[i][j] = \'#\';  // Mark the current cell as visited to avoid revisiting it\n        \n        // Explore neighbors in all four directions\n        bool op1 = search(i + 1, j, n, m, board, k + 1, word);  // Down\n        bool op2 = search(i - 1, j, n, m, board, k + 1, word);  // Up\n        bool op3 = search(i, j + 1, n, m, board, k + 1, word);  // Right\n        bool op4 = search(i, j - 1, n, m, board, k + 1, word);  // Left\n        \n        board[i][j] = ch;  // Restore the original character in the board\n        \n        return op1 || op2 || op3 || op4;  // Return true if any of the recursive calls return true\n    }\n\n    bool exist(vector<vector<char>>& board, string word) {\n        int n = board.size();  // Number of rows in the board\n        int m = board[0].size();  // Number of columns in the board\n        int k = word.size();  // Length of the target word\n\n        // Iterate over each cell in the board\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                // Check if the word can be formed starting from the current cell\n                if (search(i, j, n, m, board, 0, word)) {\n                    return true;  // If found, return true\n                }\n            }\n        }\n\n        return false;  // If no match is found, return false\n    }\n};\n```
['Array', 'Backtracking', 'Matrix', 'C++']