2025-07-20 13:53:28 +0000 UTC

class Trie:
    serial: str = ""
    children: dict[str, "Trie"]

    def __init__(self) -> None:
        self.children = dict()


class Solution:
    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:
        root = Trie()
        freq = Counter()

        for path in paths:
            cur = root
            for node in path:
                if node not in cur.children:
                    cur.children[node] = Trie()
                cur = cur.children[node]

        
        def construct(node: Trie) -> None:
            if not node.children:
                return

            serial: list[str] = []
            for folder, child in node.children.items():
                construct(child)
                serial.append(f"{folder}({child.serial})")

            serial.sort()
            node.serial = "".join(serial)
            freq[node.serial] += 1

        construct(root)

        ans = list()
        path = list()

        def operate(node: Trie) -> None:
            if freq[node.serial] > 1:
                return
            if path:
                ans.append(path[:])

            for folder, child in node.children.items():
                path.append(folder)
                operate(child)
                path.pop()

        operate(root)
        return ans