✅C++ solution using backtracking with explanations!
If you\u2019re interested in coding you can join my Discord Server, link in the comment section. Also if you find any mistake please let me know. Thank you!\u27
> **If you\u2019re interested in coding you can join my Discord Server, link in the comment section. Also if you find any mistake please let me know. Thank you!\u2764\uFE0F**\n> \n\n---\n\n## Explanation:\n\n### Solution 01\n\n- We are given a matrix of (m x n) and we are required to check whether the given word exists in the matrix or not!!!\n- We can solve this by Backtracking. Match character-by-character, go ahead and check if the adjacent cells match the next character, and go back if it does not match.\n- For each cell, traverse the entire matrix.\n- Check if\xA0`matrix[i][j] == word[index]`. (we are using\xA0the `index`\xA0to keep track of the characters that we have already checked in the\xA0`word`\xA0during backtracking.)\n    - If it is true, then check to repeat the same process for the adjacent cells and for the next index in the word.\n    - If it is false, then return to the previous state where we received a\xA0`true`\xA0value and then further check any remaining and unvisited cells.\n- **Time complexity:** O(n) | *actually it\u2019s O(4n) because we traverse 4 neighbours*.\n\n---\n\n## Code:\n\n```cpp\n//Solution 01:\nclass Solution {\npublic:\n   bool exist(vector<vector<char>> &board, string word) {\n       int row=board.size(), col=board[0].size();\n       for(int i = 0 ; i < row ; ++i)\n           for(int j = 0 ; j < col ; ++j)\n               if(search(0 , i , j , board , word))\n                   return true;\n       return false;\n   }\n   bool search(int index , int x , int y , vector<vector<char>> &board , string &word)\n   {\n       if(index == word.size())\n           return true;\n       \n       if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size() || board[x][y] == \'.\') \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] = \'.\'; \n       if(search(index + 1 , x - 1 , y , board , word) || search(index + 1 , x + 1 , y , board , word) || search(index + 1 , x , y - 1 , board , word) || search(index + 1 , x , y + 1 , board , word))\n           return true;\n           \n       board[x][y] = temp;\n       return false;\n       \n   }\n   \n};\n```\n\n---\n\n> **Please upvote this solution**\n>
['Backtracking', 'Depth-First Search', 'C++']