20 line C++ 169 ms Beats 100% & Why I think this problem is not properly judged.
The following simple naive brutal force easily beats 100% C++ submission from the past 6 months!\n\nYou know why your algorithm was slower?\nBecause you are too
The following simple naive brutal force easily beats 100% C++ submission from the past 6 months!\n\n**You know why your algorithm was slower?**\n**Because you are too smart!**\n\n DO NOT memoize the intermediate results and DO NOT use trie. The additional data structure slows the algorithm down!!\n\nThis is why I think this problem is not properly judged. The judge system should favor smarter solutions, like DP (DFS with memoization) or Trie over a naive solution like mine. \n\nAnd truth to be told, this brutal force naive one is actually my 3rd attempts: Trie is MLE, DFS with memoization is too slow (220 ms)...\n```\nclass Solution {\n    vector<string> results;\n    unordered_set<string> dict;\n    int min_len = 1;\n    bool isConcatenated(string const & word)\n    {\n        if (dict.count(word)) return true;\n        for (int i =  min_len; i < word.size() - min_len + 1 ; ++ i)\n            if (dict.count(word.substr(0, i)) > 0 && isConcatenated(word.substr(i, word.size() - i)))\n                return true;\n        return false;\n    }\npublic:\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        sort(words.begin(), words.end(), [](const string &lhs, const string &rhs){return lhs.size() < rhs.size();});\n        min_len = max(1ul, words.front().size());\n        for (int i = 0; i < words.size(); dict.insert(words[i++]))\n            if (words[i].size() >= min_len * 2 && isConcatenated(words[i]))\n                results.push_back(words[i]);\n        return results;\n    }\n};\n```\n\nThis is my Trie which got a MLE\n```\n///Passed all cases but last one got a MLE (memory limit exceeded).\nstruct TrieNode\n{\n    const static char BEGC = \'`\', ENDC = \'{\';\n    TrieNode * m_children[27] = {nullptr};\n    TrieNode(char c = BEGC)\n    {\n    }\n    inline const TrieNode * operator[](char c) const\n    {\n        return m_children[c - \'a\'];\n    }\n    inline TrieNode *& operator[](char c)\n    {\n        return m_children[c - \'a\'];\n    }\n    virtual ~TrieNode ()\n    {\n        for (auto ptr : m_children)\n            delete ptr;\n    }\n};\nstruct Trie\n{\n    TrieNode* root;\n    const static char BEGC = TrieNode::BEGC, ENDC = TrieNode::ENDC;\n    virtual ~Trie()\n    {\n        delete root;\n    }\n    Trie()\n    {\n        root = new TrieNode();\n    }\n    void insert(const string & word)\n    {\n        TrieNode *cur_node_ptr = root;\n        for (const auto c : word)\n        {\n            TrieNode &cur_node = *cur_node_ptr;\n            if (cur_node[c] == nullptr)\n                cur_node[c] = new TrieNode(c);\n            cur_node_ptr = cur_node[c];\n        }\n        TrieNode &cur_node = *cur_node_ptr;\n        if (cur_node[ENDC] == nullptr)\n            cur_node[ENDC] = new TrieNode(ENDC);\n    }\n};\nclass Solution {\n    vector<string> results;\n    Trie trie;\n    bool isConcatenated(string const & word, int start)\n    {\n        TrieNode * cur_node_ptr = trie.root;\n        for (int i = start; i < word.size(); ++i)\n        {\n            TrieNode & cur_node = *cur_node_ptr;\n            if (cur_node[Trie::ENDC] != nullptr && isConcatenated(word, i))\n                return true;\n            cur_node_ptr = cur_node[word[i]];\n            if (cur_node_ptr == nullptr)\n                return false;\n        }\n        if ((*cur_node_ptr)[Trie::ENDC] != nullptr)\n            return true;\n        return false;\n    }\npublic:\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        sort(words.begin(), words.end(), [](const string &lhs, const string &rhs){return lhs.size() < rhs.size();});\n        for (auto word : words)\n        {\n            if (word.empty())\n                continue;\n            if (isConcatenated(word, 0))\n                results.push_back(word);\n            trie.insert(word);\n        }\n        return results;\n    }\n};\n```
[]