Description

Submission

class Solution {
    struct TreeNode {
        string val;
        map<string, TreeNode*> children;
        TreeNode(string val) : val(val) {} 
    };
    TreeNode* root;
    unordered_map<string, int> key2id;
    unordered_map<string, int> key2cnt;
    unordered_map<TreeNode*, string> node2key;
    vector<vector<string>> rets;

    int getId(TreeNode* node) {
        string key = "";

        for(auto x: node->children) {
            TreeNode* child = x.second;
            key += to_string(getId(child)) + "#" + child->val + "#";
        }

        if(!key2id.count(key)) {
            key2id[key] = key2id.size() + 1;
        }

        node2key[node] = key;
        ++key2cnt[key];

        return key2id[key];
    }
    
    void dfs(TreeNode* node, vector<string>& cur) {
        string key = node2key[node];
        if(key != "" && key2cnt[key] > 1) return;
        if(node->val != "/") {
            cur.push_back(node->val);
            rets.push_back(cur);
        }

        for(auto x: node->children) {
            dfs(x.second, cur);
        }

        if(node->val != "/") {
            cur.pop_back();
        }
    }
public:
    vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {
        root = new TreeNode("/");
        for(auto& path: paths) {
            TreeNode* node = root;
            for(string s: path) { 
                if(!node->children.count(s)) {
                    node->children[s] = new TreeNode(s);
                }
                node = node->children[s];
            }
        }
        getId(root);
        vector<string> cur;
        dfs(root, cur);

        return rets;
    }
};

// key = the key of each child