Hash Map of Serialized Tree Traversals
I think this can be solved using a suffix match, but it did not work - we need to account for the tree topology.\n\nSo, we build a tree first. Now, we can recur
I think this can be solved using a suffix match, but it did not work - we need to account for the tree topology.\n\nSo, we build a tree first. Now, we can recursively compare every node, but that would be tedious and, perhaps, too long. \n\nInstead we can traverse every node (DFS) and build serialized version of this traversal (e.g. "a/b/c/d"). We can then use a hashmap to lookup nodes by their serialized traversals. If we encounter the same traversal again - we can mark both nodes (the current one, and the one in the hash map) as deleted.\n\n> Note: the solution below was updated to pass the newly added test cases. We need to use a `map` instead of `unordered_map` to guarantee the same order while traversing.\n\n> The credit for the idea goes to [lzl124631x](https://leetcode.com/lzl124631x/).\n\n**C++**\n```cpp\nstruct Node {\n    bool deleted = false;\n    string name;\n    map<string, Node*> ch;\n    Node(string name = "") : name(name) {};\n    void insert(vector<string> &path, int i = 0) {\n        if (i < path.size()) {\n            auto it = ch.find(path[i]);\n            if (it == end(ch))\n                it = ch.insert({path[i], new Node(path[i])}).first;\n            it->second->insert(path, i + 1);\n        }\n    }\n    string trim(unordered_map<string, Node*> &m) {\n        string path;\n        for (auto [name, node] : ch)\n            path += node->trim(m);\n        if (!path.empty()) {\n            auto it = m.find(path);\n            if (it != end(m))\n                it->second->deleted = deleted = true;\n            else\n                m[path] = this;\n        }\n        return "(" + name + path + ")";\n    }\n    void build(vector<vector<string>>& paths, vector<string> &path) {\n        if (!deleted) {\n            if (!path.empty())\n                paths.push_back(path);\n            for (auto [name, node] : ch) {\n                path.push_back(name);\n                node->build(paths, path);\n                path.pop_back();\n            }\n        }\n    }\n};\nvector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {\n    Node r;\n    for (auto &path : paths)\n        r.insert(path);\n    paths.clear();\n    r.trim(unordered_map<string, Node*>() = {});\n    r.build(paths, vector<string>() = {});\n    return paths;\n}\n```
[]