Delete Duplicate Folders in System Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nstruct TrieNode {\n  unordered_map<string, shared_ptr<TrieNode>> children;\n  bool deleted = false;\n};\n\nclass Solution {\n public:\n  vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {\n    vector<vector<string>> ans;\n    vector<string> path;\n    unordered_map<string, vector<shared_ptr<TrieNode>>> subtreeToNodes;\n\n    ranges::sort(paths);\n\n    for (const vector<string>& path : paths) {\n      shared_ptr<TrieNode> node = root;\n      for (const string& s : path) {\n        if (!node->children.count(s))\n          node->children[s] = make_shared<TrieNode>();\n        node = node->children[s];\n      }\n    }\n\n    buildSubtreeToRoots(root, subtreeToNodes);\n\n    for (const auto& [_, nodes] : subtreeToNodes)\n      if (nodes.size() > 1)\n        for (shared_ptr<TrieNode> node : nodes)\n          node->deleted = true;\n\n    constructPath(root, path, ans);\n    return ans;\n  }\n\n private:\n  shared_ptr<TrieNode> root = make_shared<TrieNode>();\n\n  string buildSubtreeToRoots(\n      shared_ptr<TrieNode> node,\n      unordered_map<string, vector<shared_ptr<TrieNode>>>& subtreeToNodes) {\n    string subtree = "(";\n    for (const auto& [s, child] : node->children)\n      subtree += s + buildSubtreeToRoots(child, subtreeToNodes);\n    subtree += ")";\n    if (subtree != "()")\n      subtreeToNodes[subtree].push_back(node);\n    return subtree;\n  }\n\n  void constructPath(shared_ptr<TrieNode> node, vector<string>& path,\n                     vector<vector<string>>& ans) {\n    for (const auto& [s, child] : node->children)\n      if (!child->deleted) {\n        path.push_back(s);\n        constructPath(child, path, ans);\n        path.pop_back();\n      }\n    if (!path.empty())\n      ans.push_back(path);\n  }\n};\n```
['C++']