aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--delete_duplicate_folder_system.py80
-rw-r--r--remove_subfolder_filesystem.c55
-rw-r--r--remove_subfolder_filesystem.py18
3 files changed, 144 insertions, 9 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"]]))
diff --git a/remove_subfolder_filesystem.c b/remove_subfolder_filesystem.c
new file mode 100644
index 0000000..c616906
--- /dev/null
+++ b/remove_subfolder_filesystem.c
@@ -0,0 +1,55 @@
+// 1233. Remove Sub-Folders from the Filesystem
+#include "leetcode.h"
+
+/*
+ * given a list of folders 'folder', return the folders after removing all the
+ * sub-folders in those folders. you may return the answer in any order. if a
+ * 'folder[i]' is located within another 'folder[j]', it is called a sub-folder
+ * of it. a sub-folder of 'folder[j]' must start with 'folder[j]', followed by
+ * '/'. the format of a path is one ormore concatenated strings of the form: '/'
+ * followed by one or more lowercase english letters.
+ */
+
+int cmp(const void *a, const void *b) {
+ return strcmp(*(char **)a, *(char **)b);
+}
+
+char **removeSubfolders(char **folder, int folderSize, int *returnSize) {
+ qsort(folder, folderSize, sizeof(char *), cmp);
+ char **ans = (char **)malloc(folderSize * sizeof(char *));
+ int curr = strlen(folder[0]);
+ ans[0] = folder[0];
+ *returnSize = 1;
+ for (int i = 1; i < folderSize; i++) {
+ int new = strlen(folder[i]);
+ if (new <= curr || folder[i][curr] != '/' ||
+ strncmp(ans[*returnSize - 1], folder[i], curr)) {
+ curr = new;
+ ans[*returnSize] = folder[i];
+ (*returnSize)++;
+ }
+ }
+ return ans;
+}
+
+int main() {
+ char *f1[] = {"/a", "/a/b", "/c/d", "/c/d/e", "/c/f"};
+ char *f2[] = {"/a", "/a/b/c", "/a/b/d"};
+ char *f3[] = {"/a/b/c", "/a/b/ca", "/a/b/d"};
+ int rs1, rs2, rs3;
+ char **rsf1 = removeSubfolders(f1, ARRAY_SIZE(f1), &rs1);
+ char **rsf2 = removeSubfolders(f2, ARRAY_SIZE(f2), &rs2);
+ char **rsf3 = removeSubfolders(f3, ARRAY_SIZE(f3), &rs3);
+ for (int i = 0; i < rs1; i++)
+ printf("%s ", rsf1[i]); // expect: ["/a","/c/d","/c/f"]
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%s ", rsf2[i]); // expect: ["/a"]
+ printf("\n");
+ for (int i = 0; i < rs3; i++)
+ printf("%s ", rsf3[i]); // expect: ["/a/b/c","/a/b/ca","/a/b/d"]
+ printf("\n");
+ free(rsf1);
+ free(rsf2);
+ free(rsf3);
+}
diff --git a/remove_subfolder_filesystem.py b/remove_subfolder_filesystem.py
index 484831f..8270975 100644
--- a/remove_subfolder_filesystem.py
+++ b/remove_subfolder_filesystem.py
@@ -16,15 +16,15 @@ class Solution(object):
:type folder: List[str]
:rtype: List[str]
"""
- folder.sort(key=lambda x: len(x))
- vis = set()
- for i in folder:
- for j in range(2, len(i)):
- if i[j] == "/" and i[:j] in vis:
- break
- else:
- vis.add(i)
- return list(vis)
+ n = len(folder)
+ folder.sort()
+ ans = []
+ ans.append(folder[0])
+ for i in range(1, n):
+ last = ans[-1]
+ if not folder[i].startswith(last + "/"):
+ ans.append(folder[i])
+ return ans
if __name__ == "__main__":