c++(124ms 98%) sorting & Trie & memorisation
New version : fixed for new cases. In old version I want to not use memorisation, but for NEW case of test I need to do it and I done it\nRuntime: 164 ms, faste
**New version : fixed for new cases. In old version I want to not use memorisation, but for NEW case of test I need to do it and I done it**\nRuntime: 164 ms, faster than 97.29% of C++ online submissions for Concatenated Words.\nMemory Usage: 242.3 MB, less than 49.85% of C++ online submissions for Concatenated Words.\n```\nclass Trie {\npublic:\n  struct Node{\n    bool eow;\n    Node* nb[26];\n    Node(){eow = false; for(int i=0;i!=26;i++) nb[i] = NULL;}\n  };\n  Node *root;\n\n  Trie() {root = new Node(); root->eow = true;}\n  \n  void insert(string &word) {\n    Node *tmp = root;\n    \n    for(int j = 0, idx ;j < word.size(); j++)\n      if(tmp->nb[idx = word[j] - \'a\']) tmp = tmp->nb[idx];              //if this node present\n      else                                                              //if not\n        for(int idx; j != word.size(); j++, tmp = tmp->nb[idx])\n          tmp->nb[idx = word[j] - \'a\'] = new Node();\n\n    tmp->eow = true;\n  }\n    \n  bool is_concatenated(string &sample, int j, vector<int> &hash){       //check : is the sample concatenation of words from Trie ? \n    Node *tmp = root;\n    if(hash[j]) return false;                                                                        \n    hash[j] = 1;\n    for(int idx; j < sample.size(); j++){ \n      if(tmp->nb[idx = sample[j] - \'a\']) tmp = tmp->nb[idx];              \n      else return false;\n      if(tmp->eow && (j + 1 == sample.size() || is_concatenated(sample, j + 1, hash)) ) return true; \n    }\n    return false;  \n  }\n};\n\nclass Solution {\npublic:\n  vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n    sort(words.begin(), words.end(), [](string &a, string &b) -> bool{return a.size() < b.size();});\n    Trie t;\n    vector<string> answer;\n    vector<int> hash;\n    \n    for(auto &w: words){\n      hash.clear();                                                                            //hash for indexes\n      hash.resize(w.size()+1, 0);                                                      //for next word\n      if(t.is_concatenated(w,0,hash)) answer.push_back(w);\n      else t.insert(w);\n    }\n    \n    return answer;  \n  }\n};\n```\n\n**Good day !!! FOR NEW CASE OF TEST IT HAVE TLE !!! I try to fix it !!!**\nRuntime: 124 ms, faster than 98.20% of C++ online submissions for Concatenated Words.\nMemory Usage: 241.7 MB, less than 63.26% of C++ online submissions for Concatenated Words.\n**General idea:**\n**1.** Sort our words from array from the smallest to the largest and will consider from the smallest\n**2.** take our current word from array and check : is this word the concatenation of words or not ? if yes : put it into answer **AND NOT PUT INTO Trie** ; if not : add this word into Trie\n**3.** I use my own realisation of Trie from https://leetcode.com/problems/implement-trie-prefix-tree/discuss/1110993/c%2B%2B(44ms-99)-classical-(with-comments)\n```\nclass Trie {\npublic:\n  struct Node{\n    bool eow;\n    Node* nb[26];\n    Node(){eow = false; for(int i=0;i!=26;i++) nb[i] = NULL;}\n  };\n  Node *root;\n\n  Trie() {root = new Node(); root->eow = true;}\n  \n  void insert(string &word) {\n    Node *tmp = root;\n    \n    for(int j = 0, idx ;j < word.size(); j++)\n      if(tmp->nb[idx = word[j] - \'a\']) tmp = tmp->nb[idx];              //if this node present\n      else                                                              //if not\n        for(int idx; j != word.size(); j++, tmp = tmp->nb[idx])\n          tmp->nb[idx = word[j] - \'a\'] = new Node();\n\n    tmp->eow = true;\n  }\n    \n  bool is_concatenated(string &sample, int j){        //check : is the sample concatenation of words from Trie ? \n    Node *tmp = root;\n    for(int idx; j < sample.size(); j++){\n      if(tmp->nb[idx = sample[j] - \'a\']) tmp = tmp->nb[idx];              \n      else return false;\n      if(tmp->eow && (j + 1 == sample.size() || is_concatenated(sample, j + 1)) ) return true; \n    }\n    return false;  \n  }\n};\n\nclass Solution {\npublic:\n  vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n    sort(words.begin(), words.end(), [](string &a, string &b) -> bool{return a.size() < b.size();});\n    Trie t;\n    vector<string> answer;\n    \n    for(auto &w: words)\n      if(t.is_concatenated(w,0)) answer.push_back(w);\n      else t.insert(w);\n    \n    return answer;  \n  }\n};\n```
['C', 'C++']