Delete Duplicate Folders in System LeetCode solution in Python

1
class Node:
2
    def __init__(self):
3
        self.children = defaultdict(Node)
4
        self.hash = ""
5
        self.deleted = False
6

7
    def add(self, path, i=0):
8
        if i != len(path):
9
            self.children[path[i]].add(path, i + 1)
10

11
    def calc_hash(self, hashes, name="root"):
12
        for child_name, child in sorted(self.children.items()):
13
            self.hash += f"{child.calc_hash(hashes, child_name)}+"
14
        if self.hash:
15
            hashes[self.hash].append(self)
16
        return f"{name}({self.hash})"
17

18
    def to_list(self, lst, path=[]):
19
        for name, node in self.children.items():
20
            if not node.deleted:
21
                lst.append(path + [name])
22
                node.to_list(lst, path + [name])
23

24

25
class Solution:
26
    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:
27
        root = Node()
28
        for path in paths:
29
            root.add(path)
30
        hash_to_nodes = defaultdict(list)
31
        root.calc_hash(hash_to_nodes)
32
        for nodes in hash_to_nodes.values():
33
            if len(nodes) > 1:
34
                for node in nodes:
35
                    node.deleted = True
36
        res = []
37
        root.to_list(res)
38
        return res