首页 > 其他分享 >[LeetCode] 1233. Remove Sub-Folders from the Filesystem

[LeetCode] 1233. Remove Sub-Folders from the Filesystem

时间:2023-02-08 01:12:35浏览次数:70  
标签:Folders folders Sub 1233 list 文件夹 folder leetcode

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 }

 

LeetCode 题目总结

标签:Folders,folders,Sub,1233,list,文件夹,folder,leetcode
From: https://www.cnblogs.com/cnoodle/p/17100285.html

相关文章