[Simple & Efficient][C++] Trie + Hashing
\nclass Solution {\n\tusing ull = unsigned long long;\n\n\tstruct hash_t {\n\t\tstatic constexpr ull base = 31, begin = 27, end = 28;\n\t\tull value, coeff;\n\t
```\nclass Solution {\n\tusing ull = unsigned long long;\n\n\tstruct hash_t {\n\t\tstatic constexpr ull base = 31, begin = 27, end = 28;\n\t\tull value, coeff;\n\t\thash_t() : value(0), coeff(1) {}\n\t\thash_t(ull value, ull coeff) : value(value), coeff(coeff) {}\n\t\thash_t(string_view s) : hash_t() {\n\t\t\tfor (char c : s)\n\t\t\t\taggregate({ ull(c - \'a\' + 1), base });\n\t\t}\n\t\tvoid aggregate(hash_t that) {\n\t\t\tvalue = that.coeff * value + that.value;\n\t\t\tcoeff *= that.coeff;\n\t\t}\n\t};\n\n\tstruct folder_t {\n\t\thash_t hash, name_hash;\n\t\tvector<string>* path;\n\t\tmap<ull, folder_t> children;\n\n\t\tvoid create_folders(vector<vector<string>>& paths) {\n\t\t\tfor (auto& path : paths) {\n\t\t\t\tauto* current = this;\n\t\t\t\tfor (const auto& folder : path) {\n\t\t\t\t\thash_t name_hash{ folder };\n\t\t\t\t\tcurrent = &current->children[name_hash.value];\n\t\t\t\t\tcurrent->name_hash = name_hash;\n\t\t\t\t}\n\t\t\t\tcurrent->path = &path;\n\t\t\t}\n\t\t\tpath = nullptr;\n\t\t}\n\n\t\tvoid compute_hashes(unordered_map<ull, int> &hash_to_count) {\n\t\t\thash.aggregate({ hash_t::begin, hash_t::base });\n\t\t\tfor (auto& child : children) {\n\t\t\t\tchild.second.compute_hashes(hash_to_count);\n\t\t\t\thash.aggregate(child.second.name_hash);\n\t\t\t\thash.aggregate(child.second.hash);\n\t\t\t}\n\t\t\thash.aggregate({ hash_t::end, hash_t::base });\n\t\t\tif (children.size() != 0)\n\t\t\t\t++hash_to_count[hash.value];\n\t\t}\n\n\t\tvoid compute_paths(unordered_map<ull, int>& hash_to_count, unordered_set<vector<string>*>& paths_to_keep) {\n\t\t\tif (hash_to_count[hash.value] > 1)\n\t\t\t\treturn;\n\t\t\tif (path != nullptr)\n\t\t\t\tpaths_to_keep.insert(path);\n\t\t\tfor (auto& child : children)\n\t\t\t\tchild.second.compute_paths(hash_to_count, paths_to_keep);\n\t\t}\n\t};\n\npublic:\n\tvector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {\n\t\tfolder_t root;\n\t\tunordered_map<ull, int> hash_to_count;\n\t\tunordered_set<vector<string>*> paths_to_keep;\n\t\troot.create_folders(paths);\n\t\troot.compute_hashes(hash_to_count);\n\t\troot.compute_paths(hash_to_count, paths_to_keep);\n\t\tpaths.erase(remove_if(paths.begin(), paths.end(), [&](auto& path) { return paths_to_keep.count(&path) == 0; }), paths.end());\n\t\treturn paths;\n\t}\n};\n```
[]