(C++) 472. Concatenated Words
\n\nclass TrieNode {\npublic: \n    TrieNode* children[26] = {nullptr}; \n    bool word = false; \n    ~TrieNode() {\n        for (auto& child : children) \n   
\n```\nclass TrieNode {\npublic: \n    TrieNode* children[26] = {nullptr}; \n    bool word = false; \n    ~TrieNode() {\n        for (auto& child : children) \n            delete child; \n    }\n}; \n\nclass Trie {\n    TrieNode* root = nullptr; \npublic: \n    Trie() { root = new TrieNode(); }\n    \n    ~Trie() { delete root; }\n    \n    void insert(string word) {\n        TrieNode* node = root; \n        for (int i = word.size()-1; i >= 0; --i) {\n            if (!node->children[word[i] - \'a\'])\n                node->children[word[i] - \'a\'] = new TrieNode(); \n            node = node->children[word[i] - \'a\']; \n        }\n        node->word = true; \n    }\n    \n    bool search(string word) {\n        vector<bool> dp(1 + word.size()); \n        dp[0] = true; \n        for (int i = 0; i < word.size(); ++i) {\n            TrieNode* node = root; \n            for (int j = i; j >= 0; --j) {\n                if (!node->children[word[j] - \'a\']) break; \n                node = node->children[word[j] - \'a\']; \n                if (dp[j] && node->word) {\n                    dp[i+1] = true; \n                    break; \n                }\n            }\n        }\n        return dp.back(); \n    }\n}; \n\n\nclass Solution {\npublic:\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        sort(words.begin(), words.end(), [](const string& w1, const string& w2) { return (w1.size() < w2.size()); });\n        vector<string> ans;\n        \n        Trie* trie = new Trie(); \n        for (auto& word : words) \n            if (word.size()) {\n                if (trie->search(word)) ans.push_back(word); \n                trie->insert(word); \n            }\n        \n        delete trie; \n        return ans;\n    }\n};\n```
['C']