DFS+ Backtracking|Trie| Frequency Count||27ms Beats 98.55%
Intuition\n Describe your first thoughts on how to solve this problem. \nDFS+ Backtracking\n\nLater try other better approach.\n2nd approach is Trie+DFS+Backtra
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDFS+ Backtracking\n\nLater try other better approach.\n2nd approach is Trie+DFS+Backtracking; with some improvement, there is no need extra handeling for edge cases. Good for pratice for implementing Trie! Almost the same speed like 1st one.\n\n3rd approach is the 1st one with checking on frequency counting before performing DFS function which can exclude some impossible cases & becomes much faster with a speed-up x 180/27 ~6.66666666667\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse DFS in 4 directions to solve.\nThe implementation uses marking with `@` for the visited grid & backtracking.\n\n# C++ DFS+backtracking||180ms Beats 95.61%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    int n, m, s;\n    bool dfs (int i, int j, int k, vector<vector<char>>& board, string& word)\n    {\n        if (i < 0 || i >= n || j < 0 || j >= m ||board[i][j] != word[k])\n            return 0;\n        if (k == s-1)\n            return 1;\n        char recover=board[i][j];\n        board[i][j] = \'@\';\n        bool a1 = dfs(i+1, j, k+1, board, word);\n        bool a2 = dfs(i, j+1, k+1, board, word);\n        bool a3 = dfs(i-1, j, k+1, board, word);\n        bool a4 = dfs(i, j-1, k+1, board, word);\n        board[i][j] = recover; // backtracking\n        return a1 || a2 || a3 || a4;\n    }\n\n    bool exist(vector<vector<char>>& board, string& word) {\n        n = board.size();\n        m = board[0].size();\n        s = word.size();\n        \n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                if (dfs(i, j, 0, board, word)) return 1;\n            }\n        }\n        return 0;\n    }\n};\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n\n```\n# C++ using  Trie+DFS+Backtracking||176ms Beats 95.98%\nTrie struct with constructor, destructor & insert. What\'s to do is the searching, which uses DFS+backtracking!\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nNode->insert(word): $O(|word|)$\nDFS: $O(nm4^k)$ where $k$=average searching, $k$ might be very small, or near $|word|$.\nIn total:  $O(|word|+nm4^k)$\n\n# revised C++ Code no need for handeling edge case\n```\n#pragma GCC optimize("O3", "unroll-loops")\nconst int N=58;// \'z\'-\'A\'+1=122-65+1=58\nstruct Trie {\n    Trie* next[N];\n    bool isEnd = 0;\n\n    Trie() {\n        fill(next, next+N, (Trie*)NULL);\n    }\n\n    ~Trie() {\n    //    cout<<"Destructor\\n";\n        for (int i=0; i<N; ++i) {\n            if (next[i] !=NULL) {\n                delete next[i];\n            }\n        }\n    }\n\n    void insert(string& word) {\n        Trie* Node=this;\n        for(char c: word){\n            int i=c-\'A\';\n            if(Node->next[i]==NULL)\n                Node->next[i]=new Trie();\n            Node=Node->next[i];\n        }\n        Node->isEnd=1;\n    }\n};\n\nclass Solution {\npublic:\n    int n, m, s;\n    Trie trie;\n    bool dfs (int i, int j, vector<vector<char>>& board, Trie* Node)\n    {\n        if (i < 0 || i >= n || j < 0 || j >= m )\n            return 0;\n    //    if (Node->isEnd)\n    //        return 1;\n        int index=board[i][j]-\'A\';\n        Node=Node->next[index];\n        if (!Node) return 0;\n        board[i][j]=\'_\';// ascii code 95 for \'_\' is between \'Z\' & \'a\'\n        if (Node->isEnd) return 1;\n        bool a1 = dfs(i+1, j, board, Node);\n        bool a2 = dfs(i, j+1, board, Node);\n        bool a3 = dfs(i-1, j, board, Node);\n        bool a4 = dfs(i, j-1, board, Node);\n        board[i][j]=\'A\'+index; // Backtracking\n        return a1 || a2 || a3 || a4;\n    }\n\n    bool exist(vector<vector<char>>& board, string& word) {\n        n = board.size();\n        m = board[0].size();\n        s = word.size();\n    //    if (n==1 && m==1 && s==1)//edge case \n    //        return board[0][0]==word[0];\n        Trie* Node=new Trie();\n        Node->insert(word);\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                if (dfs(i, j, board, Node)) return 1;    \n            }\n        }\n        return 0;\n    }\n};\n\n\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n\n  \n```\n# C++ DFS+backtracking+Frequency Count||27ms Beats 98.55%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    int n, m, s;\n    bool dfs (int i, int j, int k, vector<vector<char>>& board, string& word)\n    {\n        if (i < 0 || i >= n || j < 0 || j >= m ||board[i][j] != word[k])\n            return 0;\n        if (k == s-1)\n            return 1;\n        char recover=board[i][j];\n        board[i][j] = \'@\';\n        bool a1 = dfs(i+1, j, k+1, board, word);\n        bool a2 = dfs(i, j+1, k+1, board, word);\n        bool a3 = dfs(i-1, j, k+1, board, word);\n        bool a4 = dfs(i, j-1, k+1, board, word);\n        board[i][j] = recover; // backtracking\n        return a1 || a2 || a3 || a4;\n    }\n\n    bool exist(vector<vector<char>>& board, string& word) {\n        n = board.size();\n        m = board[0].size();\n        s = word.size();\n        int freq[58]={0};\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++)\n                freq[board[i][j]-\'A\']++;\n        }\n        for (char c: word) //Exclude the impossible cases\n            if(--freq[c-\'A\']<0) return 0;\n        \n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                if (dfs(i, j, 0, board, word)) return 1;\n            }\n        }\n        return 0;\n    }\n};\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['String', 'Backtracking', 'Depth-First Search', 'Trie', 'C++']