Beats 75% in Java
Intuition\nDirectories that are duplicate are the ones that have exacly the same structure of subdirectories. So the dir that should be marked for deletion is d
# Intuition\nDirectories that are duplicate are the ones that have exacly the same structure of subdirectories. So the dir that should be marked for deletion is defined by a hash of all it\'s subdirectories.\n\n# Approach\n1. Build a trie\n2. Each node should have a hash that comprises of all the children, for example A(X()+B()) where A is parent dir and has two empty subdirs X and B\n3. Collect all hashes into a Map<ChildrenHash, List<Dir>>\n4. Find ChildrenHash that have more than 1 Dir\n5. Prune all duplicated Dirs found in step 4\n6. Serialize the Trie \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```java []\nclass Solution {\n    class Dir {\n        Map<String, Dir> children = new HashMap<>();\n        String name;\n        Dir parent;\n        String childrenHash = null;\n\n        @Override\n        public String toString() {\n            return name;\n        }\n\n        Dir(Dir parent, String name) {\n            this.parent = parent;\n            this.name = name;\n        }\n\n        String hash() {\n            if (childrenHash != null) {\n                return childrenHash;\n            }\n\n            if (children.isEmpty()) {\n                return "";\n            }\n\n            List<Dir> childList = new ArrayList<>(children.values());\n            Collections.sort(childList, (a, b) -> a.name.compareTo(b.name));\n\n            String[] parts = new String[childList.size()];\n            int i = 0;\n            for (Dir chDir : childList) {\n                parts[i++] = chDir.name + "(" + chDir.hash() + ")";\n            }\n\n            childrenHash = String.join("+", parts);\n            return childrenHash;\n        }\n\n        void add(List<String> path) {\n            Dir cur = this; // A\n\n            for (String part : path) { // A B C\n                if (!cur.children.containsKey(part)) {\n                    cur.children.put(part, new Dir(cur, part)); \n                }\n\n                cur = cur.children.get(part);\n            }\n        }\n    }\n\n    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {\n        Dir root = new Dir(null, "/");\n\n        for (List<String> path : paths) {\n            root.add(path);\n        }\n\n        // group duplicate leaves\n        Map<String, List<Dir>> hashes = new HashMap<>();\n        collectHashes(root, hashes);\n\n        for (List<Dir> hashDirs : hashes.values()) {\n            if (hashDirs.size() > 1) {\n                // prune\n                for (Dir dir : hashDirs) { // for each dir in hash list\n                    dir.parent.children.remove(dir.name);\n                }\n            }\n        }\n\n        List<List<String>> res = new ArrayList<List<String>>();\n        serialize(root, res, new ArrayList<String>());\n        return res;\n    }\n\n    void serialize(Dir dir, List<List<String>> res, List<String> path) {\n        List<String> entry = new ArrayList<>(path); // shallow copy\n\n        if (dir.parent != null) {\n            entry.add(dir.name);\n            res.add(entry);\n        }\n\n        for (Dir child : dir.children.values()) {\n            serialize(child, res, entry);\n        }\n    }\n\n    void collectHashes(Dir dir, Map<String, List<Dir>> leaves) {\n        if (dir.hash().isEmpty()) { // skip nodes with no children\n            return;\n        }\n        \n        leaves.computeIfAbsent(dir.hash(), k -> new ArrayList<>());\n        leaves.get(dir.hash()).add(dir);\n\n        for (Dir child : dir.children.values()) {\n            collectHashes(child, leaves);\n        }\n    }\n}\n```
['Java']