✅☑️ Best C++ Solution Ever || Backtracking || Matrix || String || One Stop Solution.
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can solve this problem using Matrix + Backtracking.\n\n# Approach\n Describe your ap
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can solve this problem using Matrix + Backtracking.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can easily understand the approach by seeing the code which is easy to understand with comments.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime Complexity:  O(N*M*4^L), where L is the length of the word. And we are searching for the letter N*M times in the worst case. Here 4 in 4^K is because at each level of our decision tree we are making 4 recursive calls which equal 4^K in the worst case.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSpace Complexity : O(L) : where L is the length of the given word. This space is used for recursion stack.\n\n# Code\n```\n/*\n\n    Time Complexity:  O(N*M*4^L), where L is the length of the word. And we are searching for the letter N*M\n    times in the worst case. Here 4 in 4^K is because at each level of our decision tree we are making 4\n    recursive calls which equal 4^K in the worst case.\n\n    Space Complexity : O(L) : where L is the length of the given word. This space is used for recursion stack.\n\n    Solved using Matrix + Backtracking.\n\n*/\n\nclass Solution {\nprivate:\n    bool checkWordPresent(vector<vector<char>>& board, string word, int n, int m, int row, int col, int index){\n        if(index == word.size()){\n            return true;\n        }\n        if(row < 0 || col < 0 || row >= n || col >= m || board[row][col] != word[index]){\n            return false;\n        }\n        char temp = board[row][col];\n        board[row][col] = \'*\';\n        bool ans1 = checkWordPresent(board, word, n, m, row+1, col, index+1);\n        bool ans2 = checkWordPresent(board, word, n, m, row, col+1, index+1);\n        bool ans3 = checkWordPresent(board, word, n, m, row-1, col, index+1);\n        bool ans4 = checkWordPresent(board, word, n, m, row, col-1, index+1);\n        board[row][col] = temp;\n        return ans1 || ans2 || ans3 || ans4;\n    }\npublic:\n    bool exist(vector<vector<char>>& board, string word) {\n        int n = board.size();\n        int m = board[0].size();\n        for(int i=0; i<n; i++){\n            for(int j=0; j<m; j++){\n                if(checkWordPresent(board, word, n, m, i, j, 0)){\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n};\n\n```\n\n***IF YOU LIKE THE SOLUTION THEN PLEASE UPVOTE MY SOLUTION BECAUSE IT GIVES ME MOTIVATION TO REGULARLY POST THE SOLUTION.***\n\n![WhatsApp Image 2023-02-10 at 19.01.02.jpeg](https://assets.leetcode.com/users/images/0a95fea4-64f4-4502-82aa-41db6d77c05c_1676054939.8270252.jpeg)
['Array', 'Backtracking', 'Matrix', 'C++']