aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-07-18 23:30:55 -0600
committerJack Sangdahl <[email protected]>2025-07-18 23:30:55 -0600
commit8f2cda0517f8d3aef1e62f0f29926a56f70216b0 (patch)
tree86f271be06385c192d59480faf35d924970a128d
parent38317d34b680f34a58fd599a3b858dd37deab83c (diff)
downloadleetcode-8f2cda0517f8d3aef1e62f0f29926a56f70216b0.tar.gz
leetcode-8f2cda0517f8d3aef1e62f0f29926a56f70216b0.zip
1233. remove sub-folders from the filesystem
-rw-r--r--remove_subfolder_filesystem.c55
-rw-r--r--remove_subfolder_filesystem.py18
2 files changed, 64 insertions, 9 deletions
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__":