C++ [Simplest Solution possible] (Beats 85% Solution)
\n// Using DFS + Backtracking\nclass Solution {\npublic:\n\t// Check the boundary cases of the board.\n    bool isSafe(int N, int M, int i, int j){\n        ret
```\n// Using DFS + Backtracking\nclass Solution {\npublic:\n\t// Check the boundary cases of the board.\n    bool isSafe(int N, int M, int i, int j){\n        return (i<N) && (i>=0) && (j>=0) && (j<M);\n    }\n    bool backtrack(vector<vector<char>>& board, string& word, int pos, int i, int j){\n        if(word[pos]!=board[i][j]){\n            return false;\n        }\n        if(pos==word.length()-1){\n            return true;\n        }\n\t\t// to avoid using of this character again in the backtracking\n        board[i][j] = \'#\';\n        if(isSafe(board.size(), board[0].size(), i+1, j)){\n            if(backtrack(board, word, pos+1, i+1, j))\n                return true;\n        }\n        if(isSafe(board.size(), board[0].size(), i-1, j)){\n            if(backtrack(board, word, pos+1, i-1, j))\n                return true;\n        }\n        if(isSafe(board.size(), board[0].size(), i, j+1)){\n            if(backtrack(board, word, pos+1, i, j+1))\n                return true;\n        }\n        if(isSafe(board.size(), board[0].size(), i, j-1)){\n            if(backtrack(board, word, pos+1, i, j-1))\n                return true;\n        }\n\t\t// Reassigning the character as backtracking is complete.\n        board[i][j] = word[pos];\n        return false;\n    }\n    bool exist(vector<vector<char>>& board, string word) {\n        for(int i=0;i<board.size();i++){\n            for(int j=0;j<board[i].size();j++){\n                if(board[i][j]==word[0])   // This condition is not necessary as it will also be checked in the backtracking function.\n                    if(backtrack(board, word, 0, i, j))\n                        return true;\n            }\n        }\n        return false;\n    }\n};\n```\nFeel free to ask any doubts in the **comment** section. \nHappy Coding :)
['Backtracking', 'Depth-First Search', 'Recursion', 'C++']