https://leetcode.com/problems/remove-sub-folders-from-the-filesystem
1233. Remove Sub-Folders from the Filesystem
给一个资料夹列表 folder 把里面的子资料夹删除后回传 可以以任何顺序回传
folder[i] 是 folder[j] 的子资料夹代表是以 folder[j] 开头且后面接着 "/"
如 "/a/b" 是 "/a" 的子资料夹 "/b" 不是 "/a/b/c" 的子资料夹
路径由 '/' 加上一个或多个小写英文字母
Example 1:
Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: "/a/b" 是 "/a" 的子资料夹 "/c/d/e" 是 "/c/d" 的子资料夹
Example 2:
Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: "/a/b/c" 和 "/a/b/d" 都是 "/a" 的子资料夹
Example 3:
Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]
Constraints:
1 <= folder.length <= 4 * 10^4
2 <= folder[i].length <= 100
folder[i] 只包含小写英文字母跟 '/'
folder[i] 总是以 '/' 开头
每个资料夹名字是唯一的
思路：
跟题目提到的一样 判断是否是其他资料夹开头并接着 '/'
然后记得要先排序
Python Code:
class Solution:
def removeSubfolders(self, folder: List[str]) -> List[str]:
sorted_folder = sorted(folder, key=lambda x: f'{x}/')
ans = []
for f in sorted_folder:
if any(f'{f}/'.startswith(f'{_}/') for _ in ans):
continue
ans.append(f)
return ans
虽然过了 不过 Runtime 也顺利拿到了最末端
然后点了一下才发现 点图可以看其他速度的 Code Sample
最快的解法差不多 但多用了 prev 更新当前查到的资料夹 就只要一层循环就好
class Solution:
def removeSubfolders(self, folder: List[str]) -> List[str]:
folder.sort()
prev = ''
ans = []
for f in folder:
if not now or not f.startswith(f'{now}/'):
ans.append(f)
now = f
return ans