C++ clean code beats 99.7%
This problem is a backtracking problem. We need to search the adjacent area for every new step.\nYou can check the function bool adjacentSearch (recursive helpe
This problem is a **backtracking problem**. We need to search the **adjacent area** for every new step.\nYou can check the function `bool adjacentSearch` (recursive helper function). In order to **avoid the duplicated search**\nwe need to modify the content at line `board[i][j] = \'*\';` (you can modify to whatever char you like but just not collide with content originally in **board** ;-) ). Then we do another level of adjacent search! \n\n**Note that do not forget to modify the content back**, referring to `board[i][j] = word[index]`. Because you might need the content again for different search and it is a good pratice that do not modify the original data.\n\n```\n// Backtracking implmentation\nclass Solution {\npublic:\n    bool exist(vector<vector<char>>& board, string word) {\n        for(int i = 0; i < board.size(); ++i)\n        {\n            for(int j = 0; j < board[0].size(); ++j)\n            {\n                if(adjacentSearch(board, word, i, j, 0))\n                    return true;\n            }\n        }\n        return false;\n    \n    }\nprotected:\n    bool adjacentSearch(vector<vector<char>>& board, const string& word, int i, int j, int index)\n    {\n        if(index == word.size()) return true; // end condition\n        if(i < 0 || j < 0 || i > board.size()-1 || j > board[0].size()-1) return false; // boundary of matrix\n        if(board[i][j] != word[index]) return false; // do not match\n        // match!\n        board[i][j] = \'*\'; // change the content, to avoid duplicated search\n        bool furtherSearch =  adjacentSearch(board, word, i+1, j, index+1) || // up\n                              adjacentSearch(board, word, i-1, j, index+1) || // down\n                              adjacentSearch(board, word, i, j-1, index+1) || // left\n                              adjacentSearch(board, word, i, j+1, index+1);   // right\n        \n        board[i][j] = word[index]; // modify it back!\n        return furtherSearch;\n    }\n};\n```
[]