c++ trie (dfs)
\nclass Solution {\npublic:\n    struct TrieNode {\n        bool last;\n        vector<TrieNode *> children;\n        TrieNode() : last(false), children(26, nul
```\nclass Solution {\npublic:\n    struct TrieNode {\n        bool last;\n        vector<TrieNode *> children;\n        TrieNode() : last(false), children(26, nullptr) {}\n    };\n    void insert(TrieNode *root, string &s) {\n        if(!root or !s.size()) return;\n        TrieNode *curr = root;\n        for(int i = 0; i < s.size(); i++) {\n            int index = s[i] - \'a\';\n            if(!curr->children[index])\n                curr->children[index] = new TrieNode();\n            curr = curr->children[index];\n        }\n        curr->last = true;\n    }\n    void util(TrieNode *root, string &res, string subres) {\n        if(!root)\n            return;\n        if(subres.size() > res.size())\n            res = subres;\n        for(int i = 0; i < 26; i++) {\n            if(root->children[i] and root->children[i]->last) {\n                subres.push_back(\'a\' + i);\n                util(root->children[i], res, subres);\n                subres.pop_back();\n            }\n        }\n    }\n    string longestWord(vector<string>& words) {\n        TrieNode *trie = new TrieNode();\n        for(auto &word: words)\n            insert(trie, word);\n        string res;\n        util(trie, res, "");\n        return res;\n    }\n};\n\n\n\n/*\n    string longestWord(vector<string>& words) {\n        unordered_set<string> s;\n        for(auto &word: words)\n            s.insert(word);\n        int size = 0;\n        string res;\n        for(auto &word : s) {\n            for(int i = 1; i <= word.size(); i++) {\n                string sub = word.substr(0, i);\n                if(s.count(sub)) {\n                    if(sub.size() > size) {\n                        size = sub.size();\n                        res = sub;\n                    } else if(sub.size() == size)\n                        res = min(res, sub);\n                } else\n                    break;\n            }\n        }\n        return res;\n    }\n*/\n\n```
[]