Easy to understand || DFS || Backtracking || C++ ✅✅🔥🔥
\n\n# Approach\n- Iterate on the each cell in grid and use DFS function.\n- in each iteration the DFS do the following:\n    - check on the word[ptr] if not equ
![image.png](https://assets.leetcode.com/users/images/cf7e63fc-e665-44a1-8887-69d7d8b580b1_1712104777.7987192.png)\n\n# Approach\n- Iterate on the each cell in grid and use DFS function.\n- in each iteration the DFS do the following:\n    - check on the word[ptr] if not equal, return false and try on another cell.\n    - if word[ptr] is equla, increse the ptr by 1 and repeat this operation from the 4 neighbor such (up, down, right, left)\n    - remember you must in each operation check if you inside grid or not.\n\n\n# Complexity\n- Time complexity: O(n * m * word Length)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(word Length)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nint dr[]{1,-1,0, 0};       \nint dc[]{0, 0,1,-1,};\nclass Solution {\npublic:\n    int n, m;\n    vector<vector<char>> _board;\n    string _word;\n    Solution()\n    {\n        ios_base::sync_with_stdio(false); \n        cin.tie(NULL); \n        cout.tie(NULL);\n    }\n    bool isValid(int r, int c)\n    {\n        if (r < 0 || r >= n)\n            return false;\n        if (c < 0 || c >= m)\n            return false;\n        return true;\n    }\n\n    bool DFS(int r, int c, int ptr)\n    {\n        if (ptr == _word.size())\n            return true;\n        \n        if (!isValid(r, c) || _board[r][c] == \'0\' || _word[ptr] != _board[r][c])\n            return false;\n        char tmp = _board[r][c];\n        _board[r][c] = \'0\';\n        for (int i = 0; i < 4; ++i)\n        {\n            if(DFS(r + dr[i], c + dc[i], ptr+1))\n                return true;\n        }\n        _board[r][c] = tmp;\n\n        return false;\n    }\n\n    bool exist(vector<vector<char>>& board, string word) {\n        n = board.size(), m = board[0].size();\n        _board = board;\n        _word = word;\n        for (int i = 0; i < n; ++i)\n        {\n            for (int j = 0; j < m; ++j)\n            {\n                if (DFS(i, j, 0))\n                    return true;\n            }\n        }\n        return false;\n    }\n\n};\n```
['Backtracking', 'Depth-First Search', 'C++']