C++ 200ms straightforward Trie+DFS solution without DP
\nclass Solution {\nprivate:\n    struct Trie\n    {\n        vector<Trie*> children{26};\n        bool end{false};\n    };\n    \n    Trie* root;\n    \n    vo
```\nclass Solution {\nprivate:\n    struct Trie\n    {\n        vector<Trie*> children{26};\n        bool end{false};\n    };\n    \n    Trie* root;\n    \n    void insert(string& s)\n    {\n        if (s.empty()) return;\n        Trie* cur = root;\n        for (char c:s)\n        {\n            if (cur->children[c-\'a\'] == nullptr)\n                cur->children[c-\'a\'] = new Trie();\n            cur = cur->children[c-\'a\'];\n        }\n        cur->end = true;\n    }\n    \n    bool dfs(Trie* root, Trie* node, string& word, int idx, int count)\n    {\n        if (!node)\n            return false;\n        \n        if (idx >= word.size())\n        {\n            if (node->end && count >=1 )\n                return true;\n            else\n                return false;\n        }\n        \n        if (node->end && dfs(root, root, word, idx, count+1))\n            return true;\n        return dfs(root, node->children[word[idx]-\'a\'], word, idx+1, count);\n    }\n    \npublic:\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        sort(words.begin(), words.end(), [](const string& w1, const string& w2) {\n            return w1.size() < w2.size();\n        });\n        \n        vector<string> ret;\n        root = new Trie();\n        \n        for(auto &w: words)\n        {\n            if (w.empty()) continue;\n            if(dfs(root, root, w, 0, 0)) \n                ret.push_back(w);\n            else \n                insert(w);\n        }\n    \n        return ret;\n    }\n};\n```\n\nThe keys to pass the unit tests.\n1) sort words.\n2) only build trie with un-concatenated words.\n3) handle empty string.
['Depth-First Search', 'Trie', 'C']