easily explained with visualization 😎| C++✔ | Java✔|Python✔|
If you find it helpful please upvote it \uD83D\uDE3F\uD83D\uDE3F\n\n---\n\n\nstep 1(from board[0][0] it checks 4 recurtion \n(up,down,left,right) one by one)\n\
# If you find it helpful please upvote it \uD83D\uDE3F\uD83D\uDE3F\n\n---\n\n```\nstep 1(from board[0][0] it checks 4 recurtion \n(up,down,left,right) one by one)\n\n```\n\n### Example - \n```\nfrom board[0][0] -> board[1][0](this one)->board[-1][0]\n->board[0][1](got the character)\n```\n\n![1.png](https://assets.leetcode.com/users/images/5add8367-d5a5-4722-8a32-256c5876f309_1712110855.7848887.png)\n```\nstep 2 (board[-1][0] and hence invalid)\n\n```\n![2.png](https://assets.leetcode.com/users/images/4b0f82b6-336f-4525-bedc-91d0f0145856_1712110868.3586597.png)\n\n\n\n```\nstep 3\n\n```\n![3.png](https://assets.leetcode.com/users/images/bc3ba236-145c-4d82-9592-74e875fb64db_1712110877.4977424.png)\n```\nstep 4\n\n```\n\n![4.png](https://assets.leetcode.com/users/images/c8a8910d-3333-4afd-ac96-f50ad843fa01_1712110889.2690933.png)\n\n```\nstep 5 (k = 3 , not 2)\n\n```\n![5.png](https://assets.leetcode.com/users/images/853b6c36-2ec4-4fbf-adef-f22522225aa3_1712110896.5772915.png)\n```\nstep 6\n\n```\n![6.png](https://assets.leetcode.com/users/images/59787d7b-10ea-4b8b-ab6d-01f9831209af_1712110903.520588.png)\n\n```\nstep 7\n\n```\n![7.png](https://assets.leetcode.com/users/images/4536063f-b920-4348-8c7b-2be90077dd72_1712110911.3348813.png)\n# Algo\n1. **Depth-First Search (DFS):**\n    - Perform a DFS on the grid starting from each cell.\n\n2. **At Each Cell `(i, j)` in the Grid:**\n    - Check if the character at `(i, j)` matches the first character of the word.\n    - If it matches:\n        - Proceed to search for the remaining characters of the word recursively by exploring adjacent cells.\n        - Continue this process until all characters of the word are found or until reaching the end of the grid.\n\n3. **During the DFS:**\n    - Use a recursive DFS function that takes the current cell `(i, j)`, the word to search for, and the index of the current character being searched in the word.\n    - Update the index to search for the next character in the word as traversing the grid.\n    - Backtrack if the character at the current cell does not match the expected character in the word.\n\n4. **If All Characters of the Word Are Found:**\n    - Return `true`.\n\n5. **If the Word Is Not Found in the Grid:**\n    - Return `false`.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    bool dfs(int i,int j,int count,vector<vector<char>>& board,string word)\n    {\n        // if we have found the whole string then count will become (word.length()==count) so return true\n        if(word.length()==count) return true;\n        \n        // check for boundary                                  // curr char is not same with word char\n        if(i<0 || i>=board.size() || j<0 || j>=board[0].size() || board[i][j] != word[count])\n            return false;\n        \n        \n        \n        char temp = board[i][j];                    // curr char\n        board[i][j] = \' \';                          // mark as visited\n        \n        \n        // up , down , left , right (possible moves)\n        bool ans = dfs(i-1,j,count+1,board,word) || \n                   dfs(i+1,j,count+1,board,word) ||\n                   dfs(i,j-1,count+1,board,word) ||\n                   dfs(i,j+1,count+1,board,word);\n        \n        board[i][j] = temp;                         // make board as it is for the upcoming calls\n        return ans;\n    }\n    \n    bool exist(vector<vector<char>>& board, string word) \n    {\n        int n = board.size();                   // rows\n        int m = board[0].size();                // cols\n        \n        for(int i=0;i<n;i++)\n        {\n            for(int j=0;j<m;j++)\n            {\n                if(board[i][j]==word[0] && dfs(i,j,0,board,word))                // whenever we found first letter of word start searching from there\n                {\n                    return true;\n                }\n            }\n        }\n        \n        return false;\n    }\n};\n```\n```java []\nclass Solution {\n    public boolean exist(char[][] board, String word) {\n        // Depth-First Search (DFS):\n        // Perform a DFS on the grid starting from each cell.\n        \n        // Iterate through each cell in the grid\n        for (int i = 0; i < board.length; i++) {\n            for (int j = 0; j < board[0].length; j++) {\n                // Start DFS from each cell to search for the word\n                if (dfs(board, word, i, j, 0))\n                    return true; // If the word is found, return true\n            }\n        }\n        // If the word is not found after searching all cells, return false\n        return false;\n    }\n    \n    // Depth-First Search (DFS) function to search for the word starting from position (i, j)\n    public boolean dfs(char[][] board, String word, int i, int j, int idx) {\n        // Check if (i, j) is out of bounds or if the character at (i, j) does not match the next character in the word\n        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(idx))\n            return false;\n        \n        // If idx reaches the end of the word, it means the entire word is found\n        if (idx == word.length() - 1)\n            return true;\n        \n        // Temporarily store the current character at (i, j)\n        char tmp = board[i][j];\n        // Mark the current cell as visited by replacing its character with a special character \'*\'\n        board[i][j] = \'*\';\n        \n        // Recursively search in adjacent cells to find the remaining characters of the word\n        boolean res = dfs(board, word, i + 1, j, idx + 1) || dfs(board, word, i - 1, j, idx + 1) ||\n                      dfs(board, word, i, j + 1, idx + 1) || dfs(board, word, i, j - 1, idx + 1);\n        \n        // Restore the character at (i, j) to its original value\n        board[i][j] = tmp;\n        \n        return res;\n    }\n}\n\n```\n```python []\nclass Solution:\n    def exist(self, board: List[List[str]], word: str) -> bool:\n        # Depth-First Search (DFS):\n        # Perform a DFS on the grid starting from each cell.\n        \n        # Define the DFS function to search for the word starting from position (i, j)\n        def dfs(board, word, i, j, idx):\n            # Check if (i, j) is out of bounds or if the character at (i, j) does not match the next character in the word\n            if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[idx]:\n                return False\n            \n            # If idx reaches the end of the word, it means the entire word is found\n            if idx == len(word) - 1:\n                return True\n            \n            # Temporarily store the current character at (i, j)\n            tmp = board[i][j]\n            # Mark the current cell as visited by replacing its character with a special character \'*\'\n            board[i][j] = \'*\'\n            \n            # Recursively search in adjacent cells to find the remaining characters of the word\n            res = dfs(board, word, i + 1, j, idx + 1) or dfs(board, word, i - 1, j, idx + 1) \\\n                or dfs(board, word, i, j + 1, idx + 1) or dfs(board, word, i, j - 1, idx + 1)\n            \n            # Restore the character at (i, j) to its original value\n            board[i][j] = tmp\n            \n            return res\n        \n        # Iterate through each cell in the grid\n        for i in range(len(board)):\n            for j in range(len(board[0])):\n                # Start DFS from each cell to search for the word\n                if dfs(board, word, i, j, 0):\n                    return True  # If the word is found, return True\n        \n        # If the word is not found after searching all cells, return False\n        return False\n\n```\n\n```\n\n```
['Array', 'String', 'Backtracking', 'Matrix', 'Python', 'C++', 'Java', 'Python3']