C++ | Simple and Detailed Explanation
Our goal is to find if the word exisits in the matrix or not. We only have to look at the adjacent cells (ignore the diagonal ones).\n\nOne quick look at the pr
Our goal is to find if the `word` exisits in the matrix or not. We only have to look at the adjacent cells (ignore the diagonal ones).\n\nOne quick look at the problem can suggest us that 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\nHow should we traverse the matrix efficiently? We need to think of a traversal approach. BFS? DFS? Both can work. But DFS will be better as it immediately checks the next node of the graph and returns if it is not needed after marking it as visited. \n\nFinal solution approach:\n1. For each cell, traverse the entire matrix.\n2. Check if `matrix[i][j] == word[index]`. (we are using `index` to keep track of the characters that we have already checked in the `word` during backtracking.)\n3. If step 2 is true, then check repeat the same process for the adjacent cells and for the next index in the word.\n4. If step 2 is false, then return to the previous state where we received a `true` value and then further check any remaining and unvisited cells.\n\n**Note:** We mark each cell as unvisited after we check all the adjacent possibilities because we might visit that cell again when we start traversing the matrix from a different source cell. You will better understand this when you solve this test case on paper. \n\n`board = [["a","b"],["c","d"]]; word = "cdba"`\n\n**Code:**\n```\nclass Solution {\nprivate:\n    int n, m;\n    vector<vector<bool>> vis;\n    bool dfs(vector<vector<char>> &board, string word, int i, int j, int index)\n    {\n        if(board[i][j] == word[index])\n        {\n            vis[i][j] = true;\n            if(index == word.length() - 1)\n                return true;\n            if(i-1 >= 0 && vis[i-1][j] == false)\n                if(dfs(board, word, i-1, j, index+1))\n                    return true;\n            if(i+1 < n && vis[i+1][j] == false)\n                if(dfs(board, word, i+1, j, index+1))\n                    return true;\n            if(j-1 >= 0 && vis[i][j-1] == false)\n                if(dfs(board, word, i, j-1, index+1))\n                    return true;\n            if(j+1 < m && vis[i][j+1] == false)\n                if(dfs(board, word, i, j+1, index+1))\n                    return true;\n            vis[i][j] = false;\n            return false;\n        }\n        return false;\n    }\npublic:\n    bool exist(vector<vector<char>>& board, string word) {\n        n = board.size();\n        m = board[0].size();\n        vis = vector<vector<bool>>(n, vector<bool>(m, false));\n        for(int i=0; i<n; i++)\n            for(int j=0; j<m; j++)\n            {\n                if(dfs(board, word, i, j, 0))\n                    return true;\n            }\n        return false;\n    }\n};\n```\n\nI hope this helps! If you need a clarification, please post it in the comments section.\n\nIf you liked my explanation, then would you be so kind as to upvote this post? It gives me motivation to explain difficult problems in a simple manner.
['Backtracking', 'Depth-First Search', 'Recursion', 'C']