aboutsummaryrefslogtreecommitdiff
path: root/delete_duplicate_folder_system.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-07-19 18:42:03 -0600
committerJack Sangdahl <[email protected]>2025-07-19 18:42:03 -0600
commit47bee99eb4f23e27ad973d2acebe911bf21d09c4 (patch)
tree8e47d4eba9e0024918047069d07f5d55c32ab5e7 /delete_duplicate_folder_system.py
parent8f2cda0517f8d3aef1e62f0f29926a56f70216b0 (diff)
downloadleetcode-master.tar.gz
leetcode-master.zip
1948. delete duplicate folders in systemHEADmaster
Diffstat (limited to 'delete_duplicate_folder_system.py')
-rw-r--r--delete_duplicate_folder_system.py80
1 files changed, 80 insertions, 0 deletions
diff --git a/delete_duplicate_folder_system.py b/delete_duplicate_folder_system.py
new file mode 100644
index 0000000..b1a682e
--- /dev/null
+++ b/delete_duplicate_folder_system.py
@@ -0,0 +1,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"]]))