图解LeetCode——1233. 删除子文件夹

一、题目

• 你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。
• 如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。
• 文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：'/' 后跟一个或者多个小写英文字母。例如，"/leetcode" 和 "/leetcode/problems" 都是有效的路径，而空字符串和 "/" 不是。

二、示例

2.1> 示例 1：

【输入】folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]

【输出】["/a","/c/d","/c/f"]

【解释】"/a/b" 是 "/a" 的子文件夹，而 "/c/d/e" 是 "/c/d" 的子文件夹。

2.2> 示例 2：

【输入】folder = ["/a","/a/b/c","/a/b/d"]

【输出】["/a"]

【解释】文件夹 "/a/b/c" 和 "/a/b/d" 都会被删除，因为它们都是 "/a" 的子文件夹。

2.3> 示例 3：

【输入】 folder = ["/a/b/c","/a/b/ca","/a/b/d"]

【输出】 ["/a/b/c","/a/b/ca","/a/b/d"]

提示：

• 1 <= folder.length <= 4 * 10^4
• 2 <= folder[i].length <= 100
• folder[i] 只包含小写字母和 '/'
• folder[i] 总是以字符 '/' 起始
• 每个文件夹名都是 唯一 的

三、解题思路

• 根据题目描述，我们要删除所有的子目录，然后将文件夹列表 folder中剩余的目录输出即可。那么假设我们有一个目录/a，那么所有以/a开头的路径都是它的子目录，如下所示：

【主目录】/a

【子目录】/a/a，/a/b，/a/b/c，/a/b/d/e/f/g，……

• 那么针对如上规则，我们首先需要做的就是对无序的文件夹列表 folder执行排序操作，当排序完毕后，相关的主目录和子目录就会被排列在一起。遍历排序后的文件列表folder，然后我们执行如下操作：

【变量说明】

• 遍历的每个folder元素用folder[i]表示；
• 最终结果集合以result表示；
• result中最后一个元素以result(last)表示；

• 执行逻辑：

• case1：如果result为空，则直接将folder[0]保存到result中；
• case2：如果result(last)满足folder[i]的前缀，则说明folder[i]属于子目录，i执行加1，遍历下一个目录；
• case3：如果result(last)不满足folder[i]的前缀，则说明folder[i]属于主目录，将folder[i]保存到result中，然后i执行加1，遍历下一个目录；
• 当遍历完所有folder列表后，result中存储的就是所有主目录。

• 以上就是这道题的解题思路，下面我们以输入folder是["/c/d","/a/ab","/a","/c/d/e","/a/b","/c/f/d","/c/f"]为例，看一下具体的处理过程：

四、代码实现

publicclassSolution {
publicList<String>removeSubfolders(String[] folder) {
Arrays.sort(folder);
List<String>result=newArrayList<>();
result.add(folder[0]);
for (inti=1; i<folder.length; i++) {
StringBuildersb=newStringBuilder(result.get(result.size() -1)).append("/");
if (!folder[i].startsWith(sb.toString())) result.add(folder[i]);
        }
returnresult;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」