Given a list of folders folder
, return the folders after removing all 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.
The format of a path is one or more concatenated strings of the form: '/'
followed by one or more lowercase English letters.
- For example,
"/leetcode"
and"/leetcode/problems"
are valid paths while an empty string and"/"
are not.
Example 1:
Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"] Output: ["/a","/c/d","/c/f"] Explanation: Folders "/a/b" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.
Example 2:
Input: folder = ["/a","/a/b/c","/a/b/d"] Output: ["/a"] Explanation: Folders "/a/b/c" and "/a/b/d" will be removed because they are subfolders of "/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 * 104
2 <= folder[i].length <= 100
folder[i]
contains only lowercase letters and'/'
.folder[i]
always starts with the character'/'
.- Each folder name is unique.
删除子文件夹。
你是一位系统管理员,手里有一份文件夹列表 folder,你的任务是要删除该列表中的所有 子文件夹,并以 任意顺序 返回剩下的文件夹。
如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下,那么 folder[i] 就是 folder[j] 的 子文件夹 。
文件夹的「路径」是由一个或多个按以下格式串联形成的字符串:'/' 后跟一个或者多个小写英文字母。
例如,"/leetcode" 和 "/leetcode/problems" 都是有效的路径,而空字符串和 "/" 不是。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/remove-sub-folders-from-the-filesystem
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路是对 input 数组排序,然后看之后的路径是否 startsWith 之前的路径。注意 Arrays.sort() 函数,对 string array 是做字典序的排序,所以比如第一个例子,
["/a","/a/b","/c/d","/c/d/e","/c/f"]
排完序之后是这样的,
/a
/a/b
/c/d
/c/d/e
/c/f
所以当我们遇到一个子目录的时候,他的根目录应该就是前面一个字符串;如果不是,则说明当前的目录是一个根目录。
时间O(nlogn)
空间O(n) - output list
Java实现
1 class Solution { 2 public List<String> removeSubfolders(String[] folder) { 3 LinkedList<String> list = new LinkedList<>(); 4 Arrays.sort(folder); 5 for (String f : folder) { 6 if (list.isEmpty() || !f.startsWith(list.peekLast() + '/')) { 7 list.offer(f); 8 } 9 } 10 return list; 11 } 12 }
标签:Folders,folders,Sub,1233,list,文件夹,folder,leetcode From: https://www.cnblogs.com/cnoodle/p/17100285.html