[ CPP ][ Trie + DFS ] Memory 100% and Runtime 92%
Explanation:\nAlongwith trie I keep a "we" (Word Ending) array to mark which nodes in the trie represent ending of a word. In case the next node while doing the
**Explanation**:\nAlongwith trie I keep a "we" (Word Ending) array to mark which nodes in the trie represent ending of a word. In case the next node while doing the DFS isn\'t a word ending, for sure it is not going to lead to an answer, so we can prune.\nUsing an array instead of struct for trie reduces memory consumption and also improves performance. To learn how to represent tries (as well as Segment Trees for that matter), please give this a reading: https://www.commonlounge.com/discussion/f0a9acb28617471cb286d84c68a0d210 .\nWe do a DFS from left to right, thus, if a string of length ml (max_len) is found later, it for sure will be lexicographically larger than the previous answer. So, we can ignore it.\n\n**Code**\n```\nclass Solution {\npublic:\n    int trie[30003][26];\n    bool we[30003];\n    int next = 1;\n    \n    string ans = "";\n    int ml = 0;\n    \n    void insert(string &word){\n        int now = 1;\n        int n = word.size();\n        \n        for(int i = 0; i < n; ++i){\n            if(trie[now][word[i] - \'a\'] == -1){\n                trie[now][word[i] - \'a\'] = ++next;\n            }\n            now = trie[now][word[i] - \'a\'];\n        }\n        we[now] = true;\n    }\n    \n    void dfs(int nd, int clen, string &c_s){\n        if(clen > ml){\n            ml = clen;\n            ans = c_s;\n        }\n        \n        for(int i = 0; i < 26; ++i){\n            if(trie[nd][i] != -1 and we[trie[nd][i]]){\n                c_s.push_back(static_cast<char>(\'a\' + i));\n                dfs(trie[nd][i], clen + 1, c_s);\n                c_s.pop_back();\n            }\n        }\n    }\n    \n    string longestWord(vector<string>& words) {\n        memset(trie, -1, sizeof trie);\n        memset(we, 0, sizeof we);\n        \n        next = 1;\n        \n        for(auto &w: words){\n            insert(w);\n        }\n        \n        ans = "";\n        ml = 0;\n        \n        string a = "";\n        \n        dfs(1, 0, a);\n        \n        return ans;\n    }\n};\n```
[]