Python solution: JSON-style hashing of all subtrees
Intuition\r\n Describe your first thoughts on how to solve this problem. \r\nInitially I tried to build a Trie with the words reversed, but very soon I found it
# Intuition\r\n<!-- Describe your first thoughts on how to solve this problem. -->\r\nInitially I tried to build a Trie with the words reversed, but very soon I found it gives wrong answers. And there are interesting testcases which essentially requires serialization of subtrees\r\n# Approach\r\n<!-- Describe your approach to solving the problem. -->\r\nI chose the JSON style serialization because it\'s very commonly used. One must remember to use sorted children keys for hashing though. To handle leaves properly, I used a second dfs while keeping track of which node I already trimmed. \r\n# Code\r\n```\r\nfrom typing import List\r\n\r\n\r\nclass Solution:\r\n    \'\'\'\r\n    This question is about serializing a node\'s children, and removing nodes with identical children\r\n    Looking at the example, we notice the answer always is a subset of paths. So we need to decide which to delete.\r\n    To serialize a subtree, we use the JSON convention: for example, subtree of the root in examples can be represented by\r\n    1: [{a:b},{c:b},{d:a}]\r\n    2: [{a:{b:{x:y}}},{c:b},{w:y}]\r\n    3: [{a:b},{c:d}]\r\n    We can sort paths by length first\r\n    Then for each increment length, recognize the parent of each node, build the graph\r\n    Then dfs from the top: for eacb children, serialize the subtree.\r\n    Save the serialization as key in dict and delete node with keys that appear more than once.\r\n    \'\'\'\r\n    \r\n    def dfs(self, node):\r\n        n = len(self.graph[node])\r\n        nodesSorted = sorted(self.graph[node], key = lambda x: self.paths[x][-1])\r\n        result = ""\r\n        if n > 0: result += ":"\r\n        if n > 1: result += "["\r\n        for i in range(n):\r\n            result += "{"\r\n            result += self.dfs(nodesSorted[i])\r\n            result += "}"\r\n            if i < n - 1: result += ","\r\n        if n > 1: result += "]"\r\n\r\n        if result: \r\n            if result not in self.subtreeIndexMap:\r\n                self.subtreeIndexMap[result] = set()            \r\n            self.subtreeIndexMap[result].add(node)\r\n        return self.paths[node][-1] + result\r\n\r\n    def dfsThrow(self, node):\r\n        self.KeysToThrow.add(node)\r\n        for child in self.graph[node]:\r\n            if child not in self.KeysToThrow:\r\n                self.dfsThrow(child)\r\n\r\n    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\r\n        data = [[len(path), i] for i, path in enumerate(paths)]\r\n        data.sort()\r\n        self.paths = paths\r\n        n = len(data)\r\n        self.graph = [[] for i in range(n)]\r\n        j = 0\r\n        cur = 0\r\n        prev = set()\r\n        serializedPathToIndex = {}\r\n        self.subtreeIndexMap = {}\r\n        dfsStartNodes = set()\r\n        while j < n:\r\n            cur += 1\r\n            next = set()\r\n            while j < n and data[j][0] == cur:\r\n                pathSerialized = ",".join(paths[data[j][1]])\r\n                parentSerialized = ",".join(paths[data[j][1]][:-1])\r\n                if parentSerialized in prev:\r\n                    self.graph[serializedPathToIndex[parentSerialized]].append(data[j][1])\r\n                serializedPathToIndex[pathSerialized] = data[j][1]\r\n                next.add(pathSerialized)\r\n                j += 1\r\n            if cur == 1:\r\n                dfsStartNodes = set([serializedPathToIndex[i] for i in next])\r\n            prev = next\r\n        \r\n        for node in dfsStartNodes:\r\n            self.dfs(node)\r\n\r\n        self.KeysToThrow = set()\r\n        for indices in self.subtreeIndexMap.values():\r\n            if len(indices) > 1:\r\n                for i in indices:\r\n                    if i not in self.KeysToThrow:\r\n                        self.dfsThrow(i)\r\n        result = []\r\n        for i in range(n):\r\n            if i not in self.KeysToThrow:\r\n                result.append(paths[i])\r\n        return result\r\n```
['Python3']