aboutsummaryrefslogtreecommitdiff
path: root/delete_duplicate_folder_system.py
blob: b1a682e7a48beb60f2973a002f29abecbe158644 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
# 1948. Delete Duplicate Folders in System
from collections import defaultdict

"""
due to a bug, there are many duplicate folders in a file system. you are
given a 2d array 'paths', where 'paths[i]' is an array representing an
absolute path to the i'th folder in the file system. two folders are
identical if they contain the same non-empty set of identical subfolders and
underlying subfolder structure. the folders do not need to be at the root
level to be identical. if two or more folders are identical, then make the
folders as well as their subfolders. return the 2d array 'ans' containing the
paths of the remaining folders after deleting all the marked folders. the
paths may be returned in any order.
"""


class Node:
    def __init__(self):
        self.child = defaultdict(Node)
        self.dl = False


class Solution(object):
    def deleteDuplicateFolder(self, paths):
        """
        :type paths: List[List[str]]
        :rtype: List[List[str]]
        """

        pattern, root, ans = defaultdict(list), Node(), []

        def dfs1(node):
            key = "(" + "".join(i + dfs1(node.child[i]) for i in node.child) + ")"
            if key != "()":
                pattern[key].append(node)
            return key

        def dfs2(node, path):
            for i in node.child:
                if not node.child[i].dl:
                    dfs2(node.child[i], path + [i])
            if path:
                ans.append(path[:])

        for i in sorted(paths):
            node = root
            for j in i:
                node = node.child[j]
        dfs1(root)
        for i in pattern.values():
            if len(i) > 1:
                for j in i:
                    j.dl = True

        dfs2(root, [])
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(
        obj.deleteDuplicateFolder(
            paths=[["a"], ["c"], ["d"], ["a", "b"], ["c", "b"], ["d", "a"]]
        )
    )
    print(
        obj.deleteDuplicateFolder(
            paths=[
                ["a"],
                ["c"],
                ["a", "b"],
                ["c", "b"],
                ["a", "b", "x"],
                ["a", "b", "x", "y"],
                ["w"],
                ["w", "y"],
            ]
        )
    )
    print(obj.deleteDuplicateFolder(paths=[["a", "b"], ["c", "d"], ["c"], ["a"]]))