✅ C++ || Bakctracking dfs || Easiest Solution with explanation || Beginner Friendly
Approach\n\n          This is a very popular backtracking problem and is many times asked in faang interviews , although its not that difficult!!!\n          --
# ***Approach***\n```\n          This is a very popular backtracking problem and is many times asked in faang interviews , although its not that difficult!!!\n          ------------------------------------------------------------------------------------- \n          Let\'s understand the problem statement first!!!\n              we are given a matrix of (m x n) and we are required to check whether given word\n              exists in matrix or not!!!\n              NOTE : we can move in four directions(UP , DOWN , LEFT , RIGHT)\n          ------------------------------------------------------------------------------------- \n          Solution :\n                As the word in matrix can start at any position so we have to check for all\n                positions whether each position can be a starting point!!\n                \n                Now the logic is simple for every call we have index variable which shows how\n                much chars of word are already found in current dfs call \n                if at any point we found a mismatch between word[index] and baord[x][y] then that branch becomes invalid for us\n                \n                We use backtracking to make sure that each position/block of matrix \n                is visited once in a branch!!![important][visited check]\n```\n# ***Code***\n ```\nclass Solution {\npublic:\n    bool exist(vector<vector<char>> &board, string word) {\n        // checking for all positions\n        for(int i = 0 ; i < board.size() ; ++i)\n            for(int j = 0 ; j < board[0].size() ; ++j)\n                if(dfs(0 , i , j , board , word))\n                    return true;\n        return false;\n    }\n    bool dfs(int index , int x , int y , vector<vector<char>> &board , string &word)\n    {\n        if(index == word.size()) // word exists in matrix\n            return true;\n        \n        if(x < 0 or y < 0 or x >= board.size() or y >= board[0].size() or board[x][y] == \'.\') // boundary check + visited check\n            return false;\n        \n        if(board[x][y] != word[index])\n            return false;\n        \n        char temp = board[x][y];\n        board[x][y] = \'.\'; // marking it visited\n        \n        // Move in 4 directions[UP , DOWN , LEFT , RIGHT]\n        if(dfs(index + 1 , x - 1 , y , board , word) or dfs(index + 1 , x + 1 , y , board , word) or dfs(index + 1 , x , y - 1 , board , word) or dfs(index + 1 , x , y + 1 , board , word))\n            return true;\n            \n        board[x][y] = temp; // backtrack step\n        return false;\n        \n    }\n    \n};\n```\n# ***If you liked the Solution , Give it an Upvote :)***
['Backtracking', 'C']