Trie C++
Intuition\nTrie dfs traversal\n\n# Complexity\n- Time complexity: O(sum of length of all words)\n\n- Space complexity:O(sum of length of all words)\n\n# Code\n\
# Intuition\nTrie dfs traversal\n\n# Complexity\n- Time complexity: $$O(sum of length of all words)$$\n\n- Space complexity:$$O(sum of length of all words)$$\n\n# Code\n```\nclass Solution {\n\n    struct Trie {\n        vector<Trie*> children;\n        bool isEndOfWord;\n        Trie() {\n            children.resize(26, nullptr);\n            isEndOfWord = false;\n        }\n    }*root;\n\n    void insertToTrie(string &word) {\n        Trie* currentNode = root;\n        for(char &c : word) {\n            if(!currentNode->children[c-\'a\']) {\n                currentNode->children[c-\'a\'] = new Trie();\n            }\n            currentNode = currentNode->children[c-\'a\'];\n        }\n        currentNode->isEndOfWord = true;\n    }\n\n    void traverse(Trie* currentNode, string &cur, string &res) {\n        if(cur.size()>res.size()) {\n            res = cur;\n        }\n        for(int i=0;i<26;i++) {\n            if(currentNode->children[i] && currentNode->children[i]->isEndOfWord) {\n                cur.push_back(\'a\'+i);\n                traverse(currentNode->children[i], cur, res);\n                cur.pop_back();\n            }\n        }\n    }\n\npublic:\n    string longestWord(vector<string>& words) {\n        root = new Trie();\n        for(string &word : words) {\n            insertToTrie(word);\n        }\n        string res, cur;\n        traverse(root, cur, res);\n        return res;\n    }\n};\n```
['C++']