Backtracking || Simple Explanation with comments
Intuition\nThis problem seems to be a classic application of Depth First Search (DFS) in addition with Backtracking. We traverse the board starting from each ce
# Intuition\nThis problem seems to be a classic application of Depth First Search (DFS) in addition with Backtracking. We traverse the board starting from each cell, and at each step, we check if the current cell matches the current character of the word. If it does, we explore its neighbors recursively to find the next character of the word. If we find the entire word, we return true; otherwise, we backtrack and try other paths.\n\n# Approach\n- We iterate through each cell of the board.\n- For each cell, we start DFS from that cell to search for the given word.\n- During DFS, we check if the current cell matches the current character of the word. If it does, we proceed to explore its neighbors.\n- We mark the visited cells to avoid revisiting them.\n- If at any point during the DFS, we find the entire word, we return true.\n- If DFS cannot find the word starting from the current cell, we backtrack and explore other paths.\n- If no path leads to finding the word, we return false.\n\n# Complexity\n **Time complexity:** O(N*M*4^Len of word)\n **Space complexity:** O(1)\n\n# Code\n```\nclass Solution {\npublic:\n    // Helper function for DFS traversal\n    bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {\n        // If we have found all characters of the word, return true\n        if (k == word.size())\n            return true;\n        \n        // Boundary check and character mismatch check\n        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || word[k] != board[i][j])\n            return false;\n        \n        // Temporarily mark the current cell as visited\n        char ch = board[i][j];\n        board[i][j] = \'/\';\n        \n        // Explore the neighbors recursively\n        if (dfs(board, word, i + 1, j, k + 1) ||\n            dfs(board, word, i, j + 1, k + 1) ||\n            dfs(board, word, i - 1, j, k + 1) ||\n            dfs(board, word, i, j - 1, k + 1))\n            return true; // If any neighbor leads to finding the word, return true\n        \n        // Backtrack: Restore the original character in the current cell\n        board[i][j] = ch;\n        return false;\n    }\n    \n    // Main function to check if the word exists on the board\n    bool exist(vector<vector<char>>& board, string word) {\n        int n = board.size(), m = board[0].size();\n        // Iterate through each cell of the board\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < m; ++j) {\n                // If the current cell matches the first character of the word, start DFS from here\n                if (board[i][j] == word[0]) {\n                    if (dfs(board, word, i, j, 0)) // If DFS finds the word, return true\n                        return true;\n                }\n            }\n        }\n        // If no cell leads to finding the word, return false\n        return false;\n    }\n};\n\n```
['Array', 'String', 'Backtracking', 'Depth-First Search', 'Matrix', 'C++']