Cached hash & Merkle Tree
There are 2 major points worthy of attention in this problem.\n1. Efficient traversal of all folders (and corresponding paths)\n2. Efficient elimination of dupl
There are 2 major points worthy of attention in this problem.\n1. Efficient traversal of all folders (and corresponding paths)\n2. Efficient elimination of duplicates\n\nThe problem\'s description hints at a *trie*, but I think it is simply a general tree with possibly multiple children, which is natural to use to model a file system structure.\n\nFor point 1, it\'s obvious that we need to perform a DFS. One non-trivial thing is that subfolder names are guaranteed to be unique under the same parent folder, which enables us to use a dictionary to store its children and iterate over the `dict` during DFS.\n\nPoint 2 is what deserves elaboration. There are two sub-points to mention.\n1. In which cases are two folders *equal*?\nEquality testing is based on its subfolders (including names and substructures), but **NOT** the name of itself. To compare *substructures*, the idea of [Merkle Tree](https://en.wikipedia.org/wiki/Merkle_tree), which takes the aggregated hash of respective subfolders to decide equality of two parent folders, just fits in the problem.\n\n2. How to efficiently compute the hash value?\nMany solutions use strings. But the lengths of strings are unbounded, which may cause exceedingly large time and space costs. A better alternative is to implement a simple hash function. But such a function may be called multiple times. Instead we only compute the hashes after the tree will be no longer mutated, and store the computed hashes as an attribute of tree nodes to avoid redundant computations, which is the same idea as [652. Find Duplicate Subtrees](https://leetcode.com/problems/find-duplicate-subtrees/).\n\n```python\nclass Tree:\n\n    class Node:\n        def __init__(self, name: str):\n            self.name: str = name\n            self.children: Dict[str, \'Tree.Node\'] = {}\n\n        def __eq__(self, other: \'Tree.Node\'):\n            return self.children == other.children\n\n        def __hash__(self):\n            if not hasattr(self, \'_cached_hash\'):\n                self._cached_hash = hash(frozenset(self.children.items()))\n            return self._cached_hash\n\n        def __bool__(self):\n            return True if self.children else False\n\n        def __iter__(self):\n            """Return an iterator of pre-order traversal."""\n            yield self\n            for child in self.children.values():\n                yield from iter(child)\n\n        def gen_paths(self, cond: Callable[[\'Tree.Node\'], Any], path: List[str]) -> Generator[List[str], None, None]:\n            """Return an iterator of paths whose nodes all satisfy cond."""\n            if cond(self):\n                yield path\n                for child in self.children.values():\n                    path.append(child.name)\n                    yield from child.gen_paths(cond, path)\n                    path.pop()\n\n    _ROOT_FOLDER = \'_ROOT_FOLDER\'\n\n    def __init__(self):\n        self._root = Tree.Node(Tree._ROOT_FOLDER)\n\n    def __iter__(self):\n        yield from self._root\n\n    def insert(self, path: List[str]):\n        cur = self._root\n        for folder in path:\n            cur = cur.children.setdefault(folder, Tree.Node(folder))\n\n    def paths(self, cond: Callable[[\'Tree.Node\'], Any]) -> Generator[List[str], None, None]:\n        yield from self._root.gen_paths(cond, [])\n\n\nclass Solution:\n    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n        # Initialize file structure tree\n        tree = Tree()\n        for p in paths:\n            tree.insert(p)\n\n        # Count duplicates and mark them\n        counter = Counter()\n        for node in tree:\n            counter[node] += 1\n        for node in tree:\n            node.marked = True if node and counter[node] > 1 else False\n\n        # Collect non-empty paths\n        return [p.copy() for p in tree.paths(lambda x: not x.marked) if p]\n```
[]