Delete Duplicate Folders in System
\n# Approach\n Describe your approach to solving the problem. \nBuild the Trie Structure: Represent the file system as a trie, where each node corresponds to a 
\n# Approach\n<!-- Describe your approach to solving the problem. -->\nBuild the Trie Structure: Represent the file system as a trie, where each node corresponds to a folder. This will allow us to traverse the file structure efficiently.\n\nHashing Subfolder Structures: Traverse the trie and compute a hash for each subfolder\'s structure. The hash will represent the serialized structure of the folder and all its subfolders. We can then detect duplicates by checking if the same hash occurs multiple times.\n\nMark and Delete Duplicates: Identify the folders to delete by marking all nodes with duplicate hashes. Finally, perform a second traversal to collect the remaining non-duplicate folder paths.\n\nTrieNode Class: Represents each node in the trie with a dictionary of children, a hash value for its subtree, and a folder name.\n\nBuilding the Trie: The deleteDuplicateFolder function first constructs a trie representing the folder structure using the given paths.\n\nHashing the Subtrees: The hash_subtree function recursively computes a unique hash for each subtree, which includes the folder name and its children\'s hashes. It stores the hash in the node and updates the subtree_count dictionary.\n\nCollecting Remaining Paths: The collect_paths function performs a DFS to collect non-duplicate folder paths. If a subtree has a duplicate hash, it is skipped.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe solution runs in O(NlogN), where N is the total number of folders and subfolders. Sorting the children during hashing ensures efficiency.\n\n\n# Code\n```python []\nfrom collections import defaultdict\n\nclass TrieNode:\n    def __init__(self):\n        self.children = defaultdict(TrieNode)\n        self.hash = None  # Hash of the subtree rooted at this node\n        self.path = ""  # Used to store the folder name\n\nclass Solution(object):\n    def deleteDuplicateFolder(self, paths):\n        """\n        :type paths: List[List[str]]\n        :rtype: List[List[str]]\n        """\n        root = TrieNode()\n\n        # Step 1: Build the trie from the given paths\n        for path in paths:\n            current = root\n            for folder in path:\n                current = current.children[folder]\n            current.path = folder\n        \n        subtree_count = defaultdict(int)  # To count occurrences of each subtree hash\n        \n        # Step 2: Traverse the trie and hash each subtree\n        def hash_subtree(node):\n            if not node.children:\n                return ""  # Empty hash for leaf nodes\n            \n            # Serialize the subtree\n            children_hashes = []\n            for child_name, child_node in sorted(node.children.items()):\n                child_hash = hash_subtree(child_node)\n                # Use string concatenation instead of f-string\n                children_hashes.append(child_name + "(" + child_hash + ")")\n            \n            # Create a unique hash for the current subtree\n            node.hash = "".join(children_hashes)\n            subtree_count[node.hash] += 1\n            return node.hash\n        \n        hash_subtree(root)  # Start hashing from the root\n        \n        # Step 3: Collect non-duplicate folder paths\n        result = []\n\n        def collect_paths(node, path):\n            if subtree_count[node.hash] > 1:\n                return  # Skip this node and its subfolders as they are marked for deletion\n            \n            # If not a root node, add the path\n            if node.path:\n                result.append(list(path))  # Create a copy of the path\n            \n            # Recursively process children\n            for child_name, child_node in node.children.items():\n                path.append(child_name)\n                collect_paths(child_node, path)\n                path.pop()\n        \n        collect_paths(root, [])\n        return result\n\n```
['Python']