diff options
-rw-r--r-- | delete_duplicate_folder_system.py | 80 | ||||
-rw-r--r-- | remove_subfolder_filesystem.c | 55 | ||||
-rw-r--r-- | remove_subfolder_filesystem.py | 18 |
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__": |