[python] using dictionary of dictionaries (build tree and remove duplicates)
Approach\nFollowing are the steps to achieving what we need:\n1. Build the directory tree using dictionaries.\n2. For all the input paths which correspond to no
## Approach\nFollowing are the steps to achieving what we need:\n1. Build the directory tree using dictionaries.\n2. For all the input paths which correspond to non-leaf directories, build a subtree signature\n3. Store the parent and the subtree key against this signature in a list so that paths having same subtree signatures will go in the same list. Any such list with length more than 1 are duplicates\n4. Remove these duplicates by popping the child key from the parent dictionary.\n5. Re-construct the paths by flattening the directory tree.\n\n```\nclass Solution:\n    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n        \n        # build dir tree as a dictionary\n        root = {}\n        for path in paths:\n            node = root\n            for p in path: \n                if p not in node: node[p] = {}\n                node = node[p]\n        \n        # subtree signature... note that subtrees\' order doesn\'t matter\n        # so same signature should be generated irrespective of the ordering of subtrees\n        sign = lambda node: \'(\' + \'|\'.join([key + sign(node[key]) for key in sorted(node.keys())]) + \')\'\n\t\t\n        # derive subdir signature for all non-leaf nodes in the tree\n\t\t# put them in a map of signature to list of nodes\n        # every node is represented by a parent and its subtree key\n        subtree2node = defaultdict(list)\n        for path in paths:\n            parent = node = root\n            for segment in path: \n                parent, node = node, node[segment]\n            if node:\n                subtree2node[sign(node)].append((segment, parent))\n        \n        # delete duplicate subtrees\n\t\t# duplicates will have same signature so the corresponding list will have more than one nodes\n        for subtree in subtree2node.values():\n            if len(subtree) > 1:\n                for segment, parent in subtree:\n                    parent.pop(segment)\n        \n        # recursively construct all paths from the remaining tree\n        def flatten(node, prefix):\n            answer = []\n            for key in node:\n                path = prefix + [key]\n                answer.append(path)\n                answer.extend(flatten(node[key], path))\n            return answer\n                \n        return flatten(root, [])\n```
[]