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