[Python] Tree Hashing: assign unique ID for each unique subtree to save space cost
\nclass Solution:\n    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n        """\n        n = len(path)\n        d = len(path[i])
```\nclass Solution:\n    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n        """\n        n = len(path)\n        d = len(path[i])\n        l = len(path[i][j])\n        L = sum(l)\n        """\n        # build trie\n        # Time: O(n*d)\n        # Space: O(n)\n        root = {}\n        for path in paths:\n            curr = root\n            for d in path:\n                if d not in curr:\n                    curr[d] = {}\n                curr = curr[d]\n                \n        # hash and find duplicates\n        # Time: O(n * avg_n_children)\n        # Space: O(n + n_unique_id)\n\t\t## each time we find a unique subtree, assign a unique ID\n        subtree_id = defaultdict(None)\n        subtree_id.default_factory = subtree_id.__len__\n\t\t## group subtrees by ID. \n        duplicates = defaultdict(list)\n        def hash_(node):\n            if not node:\n                return None\n\t\t\t# sort keys and get hash code for each child\n\t\t\t# concatenate them for the hash code of current node\n            hash_code = \'\'.join([\n                f\'({child}:{hash_(node[child])})\'\n                for child in sorted(node.keys())\n            ])\n\t\t\t# get ID of the hash code, if not found, assign new ID as the length\n            id_ = subtree_id[hash_code]\n\t\t\t# update duplicate list by ID\n            duplicates[id_].append(node)\n            return id_\n\n        hash_(root)\n        \n        # mark duplicate subtrees in trie\n        for subtrees in duplicates.values():\n            if len(subtrees) == 1:\n                continue\n            for subtree in subtrees:\n                subtree[\'is_dup\'] = True\n\t\t\t\t\n        # dfs for output: generate paths for each non-duplicate folder\n        # Time: O(n)\n        # Space: O(1)\n        res = []\n        def dfs(node, path):\n\t\t\t# if current folder is makred duplicate, terminate the path\n            if \'is_dup\' in node:\n                return\n\t\t\t# if a non-empty path is found, put in result\n            if path:\n                res.append(path)\n\n            for k, v in node.items():\n                dfs(v, path + [k])\n            return \n\t\t\t\n        dfs(root, [])\n        return res\n        \n            \n```
['Depth-First Search', 'Trie', 'Python']