[Python3] Augmented Trie
Use trie to store the folders in system and augment each node with t[\'*\'] that points to the node\'s parent and t[\'**\'] that contains the folder\'s own name
Use trie to store the folders in system and augment each node with `t[\'*\']` that points to the node\'s parent and `t[\'**\']` that contains the folder\'s own name.\nTraverse the trie once to find all the leaves. The folders that contain leaves are then candidates for deletion. \nAt each iteration of the while loop we only delete duplicate folders that contain leaves or folders deleted already. If any folders are deleted, their parents are the candidates for the next iteration. \nOne tricky point is that folders contain duplicate folders but with different names are considered different. So instead of just `del parent[f]`, `leaf_ids.add(id(parent[\'*\' + f]))` adds a fake leaf folder to take that into account.\n```\nclass Solution:\n    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n        leaves = []\n        trie_lambda = lambda: collections.defaultdict(trie_lambda)\n        trie = trie_lambda()\n        trie[\'*\'] = trie[\'**\'] = \'*\'\n        \n        for p in paths:\n            t = trie\n            for f in p:\n                parent, t = t, t[f]\n                t[\'*\'] = parent\n                t[\'**\'] = f\n        \n        def traverse(t):\n            if len(t) == 2:\n                leaves.append(t)\n            else:\n                for k, v in t.items():\n                    if k[0] != \'*\':\n                        traverse(v)\n        traverse(trie)\n        \n        leaf_ids = set(id(leaf) for leaf in leaves)\n        candidates = {id(leaf[\'*\']):leaf[\'*\'] for leaf in leaves}\n        \n        while candidates:\n            new = {}\n            dup = collections.defaultdict(list)\n            for cand in candidates.values():\n                if any(id(v) not in leaf_ids for k, v in cand.items() if k[0] != \'*\'):\n                    continue\n                dup[\',\'.join(sorted(cand.keys()))].append(cand)\n            for k, v in dup.items():\n                if len(v) > 1:\n                    for cand in v:\n                        f = cand[\'**\']\n                        parent = cand[\'*\']\n                        del parent[f]\n                        leaf_ids.add(id(parent[\'*\' + f]))\n                        new[id(parent)] = parent\n            candidates = new\n        path = []\n        ans = []\n        def dfs(t):\n            for f in t:\n                if f[0] != \'*\':\n                    path.append(f)\n                    ans.append(list(path))\n                    dfs(t[f])\n                    path.pop()\n        dfs(trie)\n        return ans\n```\nDue to some confusion about the input and leaf detection I didn\'t get to finish in time for the contest :(
['Python3']