Fast and readable C++ solution using tries
Intuition\nConstruct a trie and compute a serial identifier for the nodes.\n\n# Approach\n1. Construct a trie from the input paths.\n2. Compute an identifier fo
# Intuition\nConstruct a trie and compute a serial identifier for the nodes.\n\n# Approach\n1. Construct a trie from the input paths.\n2. Compute an identifier for each node in the trie, and locate duplicates.\n3. Output nodes with unique identifiers.\n\nMost importantly, the identifier we compute in step 2 must have a 1:1 mapping with the subdirectory structure from that node. E.g. two distinct subdirectory structures cannot map to the same id, and two distinct ids cannot map to the same subdirectory structure.\n\n# Code\n```\nclass Trie {\npublic:\n    // Recursively insert a path into this Trie.\n    void insert(vector<string>::iterator current, vector<string>::iterator end) {\n        if (current != end) {\n            // Insert the rest of the path into the child node.\n            children_[*current].insert(++current, end);\n        }\n    }\n\n    // Get a string which uniquely identifies the structure of this Trie node\n    // (and all of its children), but does not include the name of this Trie node\n    // itself (because two folders with different names can still be duplicates).\n    const string& partial_id() {\n        if (!serial_id_.empty()) {\n            return serial_id_;\n        }\n        for (auto& [child_name, child] : children_) {\n            serial_id_ += child_name + "(" + child.partial_id() + "),";\n        }\n        return serial_id_;\n    }\n\n    map<string, Trie> children_;\n    string serial_id_;\n};\n\nclass Solution {\npublic:\n    vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {\n        // Build the trie.\n        Trie root;\n        for (vector<string>& path : paths) {\n            root.insert(path.begin(), path.end());\n        }\n\n        // Find the duplicates.\n        unordered_map<string, int> count;\n        count_ids(root, count);\n\n        // Find the nonduplicates.\n        vector<string> current_path;\n        vector<vector<string>> nonduplicates;\n        gather_nonduplicates(root, count, current_path, nonduplicates);\n        return nonduplicates;\n    }\n\nprivate:\n    // Recursively count the number of occurrences for each partial id\n    // in the given Trie.\n    void count_ids(Trie& current, unordered_map<string, int>& count) {\n        count[current.partial_id()]++;\n        for (auto& [child_name, child] : current.children_) {\n            count_ids(child, count);\n        }\n    }\n\n    // Traverse the tree and append non-duplicated folders to `non_duplicates`.\n    void gather_nonduplicates(Trie& current,\n                              const unordered_map<string, int>& count,\n                              vector<string>& current_path,\n                              vector<vector<string>>& nonduplicates) {\n        if (current.partial_id().empty()) {\n            // Root nodes are never considered duplicates unless\n            // their parents are also duplicates.\n            nonduplicates.push_back(current_path);\n            return;\n        }\n\n        if (count.at(current.partial_id()) != 1) {\n            // This node (and all children) is a duplicate.\n            // No need to continue traversing.\n            return;\n        }\n\n        if (!current_path.empty()) {\n            // Avoid edge case causing empy output for root node.\n            nonduplicates.push_back(current_path);\n        }\n\n        // Traverse children.\n        for (auto& [child_name, child] : current.children_) {\n            current_path.push_back(child_name);\n            gather_nonduplicates(child, count, current_path, nonduplicates);\n            current_path.pop_back();\n        }\n    }\n};\n```
['C++']