✅Easy✨||C++|| Beats 100% || With Explanation ||
\n# Approach\n Describe your approach to solving the problem. \n1. Search function:\n\n. The recursive search function explores the board to find a match for th
\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Search function:\n\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.\nThe function explores neighbors in all four directions (up, down, left, right) if the current cell matches the current character of the word.\n2. Exist function:\n\nThe 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.\nIt returns true if any match is found, indicating that the word exists on the board. Otherwise, it returns false.\n3. Marking Visited Cells:\n\n. The function marks visited cells with the character \'#\' to avoid revisiting the same cell in the recursive exploration.\n\n4. Backtracking:\n\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# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n0(N * M * 4^k)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(1)\n# Code\n```\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```
['C++']