0ms TLE_explained 100%faster
Do upvote\n# Sol #1. DFS (800ms)\n\nclass Solution {\npublic:\n    bool dfs(vector<vector<char>> &arr, string word, int k, int r, int c)//pass arr by reference\
Do upvote\n# Sol #1. DFS (800ms)\n```\nclass Solution {\npublic:\n    bool dfs(vector<vector<char>> &arr, string word, int k, int r, int c)//pass arr by reference\n    {\n        \n        if(r>=arr.size()||r<0||c>=arr[0].size()||c<0||arr[r][c] != word[k])\n            return false;\n\n            k++;\n            if(k==word.size())\n                return true;\n            \n\t\t\tarr[r][c]=\'*\'; // changed in orignal arr to avoid taking same occurence of alphabet in arr for different occurences in word\n            \n\t\t\tbool res =  dfs(arr,word,k,r+1,c) || \n\t\t\t\t\t\tdfs(arr,word,k,r-1,c) || \n\t\t\t\t\t\tdfs(arr,word,k,r,c+1) ||\n\t\t\t\t\t\tdfs(arr,word,k,r,c-1);\n            \n            arr[r][c]=word[k-1]; //as arr is passed by reference all changes must be reversed before next iteration\n        return res;\n            \n\n\n    }\n    \n    bool exist(vector<vector<char>>& arr, string word) \n    {\n        for(int i=0;i<arr.size();i++)\n            for(int j=0;j<arr[0].size();++j)\n                if(dfs(arr,word,0,i,j))\n                    return true;\n        return false;\n        \n    }\n};\n```\n* This solution will take around 800ms\n* you will get **TLE** if *arr* is passed by value like this in *dfs* function ```bool dfs(vector<vector<char>> arr, string word, int k, int r, int c) ```\n\n\n# Sol #2. DFS with Pruning  0ms sol\n```\nclass Solution \n{\n    bool dfs(vector<vector<char>> &arr, string word, int k, int r, int c)\n    {\n        \n        if(r>=arr.size()||r<0||c>=arr[0].size()||c<0||arr[r][c] != word[k])\n            return false;\n\n            k++;\n            if(k==word.size())\n                return true;\n            arr[r][c]=\'.\';\n            bool res =  dfs(arr,word,k,r+1,c) || \n\t\t\t\t\t\tdfs(arr,word,k,r-1,c) || \n\t\t\t\t\t\tdfs(arr,word,k,r,c+1) ||\n\t\t\t\t\t\tdfs(arr,word,k,r,c-1);\n            \n            arr[r][c]=word[k-1];\n        return res;\n    }\n    \npublic:\n    bool exist(vector<vector<char>>& arr, string& word) {\n        int R = arr.size(), C = arr[0].size(), N = word.size();\n\n        // Prune #1: the arr cannot contain the word.\n        if (N > R * C) return false;\n\n        // Prune #2: the arr does not contain all occurrences of the chars in the word.\n        unordered_map<char, int> occ;\n        for (auto& row : arr) for (auto& c : row) ++occ[c];\n        for (auto& c : word) if(--occ[c] < 0) return false;\n\n        // Prune #3: Find the longest prefix/suffix of the same character. If the longest\n        // suffix is longer than the longest prefix, swap the strigns (so we are less\n        // likely to have a long prefix with a lot of the same character).\n        int left = word.find_first_not_of(word[0]);\n        int right = N - word.find_last_not_of(word[N - 1]);\n        if (left > right) reverse(begin(word), end(word));\n\n        for(int i=0;i<arr.size();i++)\n            for(int j=0;j<arr[0].size();++j)\n                if(dfs(arr,word,0,i,j))\n                    return true;\n        return false;\n    }\n};\n```\n* **We use the same DFS with some prior analysis.**\n* **Prune 3 is for such cases**\n[["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"]]\n"AAAAAAAAAAAAAAB"\nit changes word to "BAAAAAAAAAAAAAA"\n![image](https://assets.leetcode.com/users/images/c4161e1c-960a-47f8-a4d1-903ae22cbbcc_1653990215.8375807.png)\n
['C', 'C++']