[C++] O(N) Trie + Merkle Tree w/ Custom Hashing (GCC std::hash has collisions)
Basically, this is my thought process:\n- Trie: I need to "compress" all the paths with their parent paths into one tree, so [a], [a,b], [a,b,c] turns into [a,b
Basically, this is my thought process:\n- Trie: I need to "compress" all the paths with their parent paths into one tree, so `[a], [a,b], [a,b,c]` turns into `[a,b,c]`. It is also good for getting the remaining paths after removal of duplicate folders.\n- Merkle Tree: Efficient computation of hashes for each subtree. Note for for getting the hash of each subtree, **we DO NOT include the subtree\'s root folder name!** This is because we only care about the structure underneath the parent folders, the names of the parent folders do not matter.\n\nOther solutions hash the traversals of the subtrees, but that is not ideal for more complicated problems because of the repeated string concatenation, which leads up to O(N^2). \n\n---\n\n```cpp\n#define vec vector\n#define umap unordered_map\n\nusing vs = vec<string>;\nusing vvs = vec<vec<string>>;\n\ntemplate <typename T, typename = void> struct is_tuple_like {\n  static constexpr bool value = false;\n};\ntemplate <typename T>\nstruct is_tuple_like<T, void_t<typename tuple_size<T>::type>> {\n  static constexpr bool value = true;\n};\ntemplate <typename T, typename = void> struct is_hashable {\n  static constexpr bool value = false;\n};\ntemplate <typename T> struct is_hashable<T, void_t<decltype(hash<T>{}(T{}))>> {\n  static constexpr bool value = true;\n};\nvec<size_t> VALS;\nstruct custom_hash {\n  static size_t getfixed(int i) {\n    while ((int)VALS.size() < i + 1)\n      if (VALS.empty())\n        VALS.push_back(\n            (size_t)chrono::steady_clock::now().time_since_epoch().count());\n      else\n        VALS.push_back(splitmix64(VALS.back()));\n    return VALS[i];\n  }\n  static size_t splitmix64(size_t x) {\n    x += (size_t)0x9e3779b97f4a7c15;\n    x = (x ^ (x >> (size_t)30)) * (size_t)0xbf58476d1ce4e5b9;\n    x = (x ^ (x >> (size_t)27)) * (size_t)0x94d049bb133111eb;\n    return x ^ (x >> (size_t)31);\n  }\n  template <typename T>\n  enable_if_t<is_hashable<T>::value, size_t> operator()(const T &t) const {\n    return splitmix64(hash<T>{}(t) + getfixed(0));\n  }\n  template <typename T>\n  enable_if_t<is_tuple_like<T>::value, size_t> operator()(const T &t) const {\n    int ic = 0;\n    size_t rh = 0;\n    apply(\n        [&](auto &&...args) {\n          ((rh ^=\n            splitmix64(hash<decay_t<decltype(args)>>{}(args) + getfixed(ic++))),\n           ...);\n        },\n        t);\n    return rh;\n  }\n};\n\nstruct trie {\n  struct node {\n    umap<string, node *> adj;\n    size_t hash = 0;\n  };\n  node *root = new node();\n  umap<size_t, int> subtrees;\n  void insert(vs &s) {\n    auto cur = root;\n    for (int i = 0; i < s.size(); i++) {\n      auto &next = cur->adj[s[i]];\n      if (!next)\n        next = new node();\n      cur = next;\n    }\n  }\n  void paths(node *cur, vs &path, vvs &ans) {\n    for (auto &[a, next] : cur->adj) {\n      if (next) {\n        path.push_back(a);\n        ans.push_back(path);\n        paths(next, path, ans);\n        path.pop_back();\n      }\n    }\n  }\n  size_t compute_merkle(node *cur) {\n    size_t combined_hash = 0;\n    for (auto &[child, next] : cur->adj) {\n      combined_hash +=\n          custom_hash{}(custom_hash{}(child) + compute_merkle(next));\n\t  // ^ We hash together the name of the children\'s folder with the hash of its\n\t  // substructures to make sure they came from the same children\n    }\n    cur->hash = custom_hash{}(combined_hash);\n    subtrees[cur->hash]++;\n    return cur->hash;\n  }\n  void delete_duplicates(node *cur) {\n    for (auto &[_, next] : cur->adj) {\n      delete_duplicates(next);\n      if (!next->adj.empty() && subtrees[next->hash] > 1) {\n        next = nullptr;\n      }\n    }\n  }\n};\n\nclass Solution {\npublic:\n  vector<vector<string>> deleteDuplicateFolder(vector<vector<string>> &paths) {\n    trie t;\n    for (auto &path : paths) {\n      t.insert(path);\n    }\n    t.compute_merkle(t.root);\n    t.delete_duplicates(t.root);\n\n    vvs ans;\n    vs path;\n    t.paths(t.root, path, ans);\n    return ans;\n  }\n};\n```
['Depth-First Search', 'Trie', 'C', 'Hash Function']