Java Trie Node + Serialization With Explanation
I want to start by saying this problem is hard, even for a hard problem. This solution took me a good 20-30 minutes just to conceptualize. You could definitely 
I want to start by saying this problem is hard, even for a hard problem. This solution took me a good 20-30 minutes just to conceptualize. You could definitely solve this problem using a directory structure with just Maps, but using Trie Nodes is a little less annoying to code IMO. If you don\'t know what a Trie Node is, you should really go read up on it and try to solve a simpler problem first. \n\n **The idea:**\n We want to build our directory structure using a generic TrieNode builder algorithm, so every directory node contains a reference to each of its child directories, in the form of a map. We will keep track of a list of indicies representing every `i` where `paths[i]` crosses through this node in our directory structure. This will come in handy later when we want to create our non-duplicate path list. \n \n Now all we need is to be able to identify two identical directory structures. From the problem description, we can tell we don\'t care about the name of the directory, but only whether all of its contents are identical to another directory somewhere else. But since every directory contains subdirectories that have their own directory structures, finding two identical structures is not trivial. The solution? Serialization. For any directory `node`, and ant of its children `child`, we can append `child.name:serialize(child)` until our serialization for node looks something like \n ```\n child1.name:serialize(child1),child2.name:serialize(child2),...childn.name:serialize(childn)\n ```\n There is one caveat here, which is that we need the children to be in lexicographic order (or any constant ordering structure) so when we serialize 2 directories with identical contents, we get the same serialization. \n \n Now that we know how to tell when 2 directories are identical, we just need to be able to correlate that to a return value. The problem asks you to return any paths that correspond to directory structures without any identical directories. This is where that list of indicies we kept while building our TrieNode graph comes in handy. If any two directories have identical contents, add all of the indicies from both nodes to our list of duplicate paths. Then just iterate over the list of paths again, adding any path at an index not in our list of duplicates.\n \n The code for this solution ends up looking like this:\n```\nclass Solution {\n    \n    class TrieNode {\n\t\t// Use TreeMap so keys stay in the same order for any 2 nodes, so when we\n\t\t// serialize 2 nodes with identical structures, we will get the same result\n        TreeMap<String, TrieNode> next;\n        List<Integer> indicies;\n        String contents;\n        \n        TrieNode() {\n            next = new TreeMap();\n            indicies = new ArrayList();\n        }\n        \n        TrieNode addChild(String dir) {\n            if (next.containsKey(dir))\n                return next.get(dir);\n            \n            next.put(dir, new TrieNode());\n            return next.get(dir);\n        }\n        \n        void addIndex(int index) {\n            indicies.add(index);\n        }\n        \n        String serialize() {\n            if (contents != null)\n                return contents;\n            \n            StringBuilder sb = new StringBuilder();\n            next.forEach((k, v) -> {\n                sb.append(k);\n                sb.append(":");\n                sb.append(v.serialize());\n\t\t\t\t// Need to use separate delimiter for same level\n                sb.append(",");\n            });\n            \n            return contents = sb.toString();\n        }\n    }\n    \n    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {\n        TrieNode root = buildTrie(paths);\n\t\t// Store the indicies of the paths that correspond to duplicate directories\n        Set<Integer> duplicates = new HashSet();\n        findDuplicates(root, new HashMap<String, List<Integer>>(), duplicates);\n        List<List<String>> res = new ArrayList();\n        for (int i = 0; i < paths.size(); ++i) {\n            if (!duplicates.contains(i))\n                res.add(paths.get(i));\n        }\n        \n        return res;\n    }\n    \n    private String findDuplicates(TrieNode node, Map<String, List<Integer>> directories, Set<Integer> dups) {\n        for (TrieNode child : node.next.values()) {\n            String key = findDuplicates(child, directories, dups);\n            if (key.isEmpty())\n                continue;\n            \n            if (directories.containsKey(key)) {\n                dups.addAll(child.indicies);\n                dups.addAll(directories.get(key));\n            } else\n                directories.put(key, child.indicies);\n        }\n        \n        return node.serialize();\n    }\n    \n    private TrieNode buildTrie(List<List<String>> paths) {\n        TrieNode root = new TrieNode();\n        for (int i = 0; i < paths.size(); ++i) {\n            TrieNode node = root;\n            for (String dir : paths.get(i)) {\n                node = node.addChild(dir);\n\t\t\t\t// Add the index so we know if this directory ends up being a \n\t\t\t\t// duplicate, we will know which paths were associated with it\n                node.addIndex(i);\n            }\n        }\n        \n        return root;\n    }\n}\n```\nPlease upvote if you liked the solution or found the explanation useful :)
[]