LeetCode 1233. 删除子文件夹

约 4 分钟
文章信息 9 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节跳动 微软 百度 华为
标签
数组 字符串 深度优先搜索 字典树
目录

题目描述

✅ 1233. 删除子文件夹

题意分析

输入是一组互不相同的绝对路径，每条都以 / 开头、由若干小写字母段拼成，段与段之间用 / 分隔，末尾不带 /。要求剔除掉那些「被列表里另一条路径包住」的目录，剩下的按任意顺序返回。

「被包住」这件事必须按整段对齐来理解，而不是按字符串前缀。/a/b 落在 /a 里面，/ab 却和 /a 毫无关系——它们只是碰巧共享了前两个字符。判断的分界点就在于紧跟着前缀的那个字符是不是分隔符。

约束里有两个信号值得留意：路径总数上限四万，单条长度上限一百，说明总字符量只有几百万，允许对每条路径做一次线性长度的比较；另外题目保证路径互不相同，因此不必操心「一条路径是不是自己的子目录」这种退化情况。边界上要考虑的是只有一条路径时直接保留、以及若干条路径共享同一个父目录时不能相互误删（/c/d 与 /c/f 平级，两条都得留）。

解法：字典序排序后过滤

核心思路

将路径按字典序排序后，父目录一定排在自己的子目录之前，而且同一父目录的所有子目录会连续出现。原因是路径字符按前缀比较：/a 先于 /a/...，而 /a/... 又会聚集在同一前缀区间。

因此扫描时只需与「最后一个保留路径」比较：

  • 若当前路径以 parent + "/" 开头，它是子目录，跳过；
  • 否则它不属于当前目录树，保留并成为新的比较基准。

循环不变量是：答案列表已经正确过滤了扫描过的路径；若当前路径存在已保留祖先，该祖先必是答案末尾。被过滤的子目录不能更新基准，否则会丢失真正的祖先。

分隔符是判断的一部分：/a/b 是 /a 的子目录，/ab 不是。只判断普通字符串前缀会误删后者。

解题步骤

  1. 按字典序排序全部路径。
  2. 依次扫描；答案为空时直接保留当前路径。
  3. 取最后一个保留路径 parent，判断当前路径是否以 parent + "/" 开头。
  4. 是则跳过，否则加入答案。

例如排序后的 ["/a", "/a/b", "/c/d", "/c/d/e", "/c/f"]：保留 /a，过滤 /a/b；保留 /c/d，过滤 /c/d/e；/c/f 与 /c/d 平级，保留。最终得到 ["/a", "/c/d", "/c/f"]。

代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        List<String> answer = new ArrayList<>();
        for (String path : folder) {
            if (answer.isEmpty()
                    || !path.startsWith(answer.get(answer.size() - 1) + "/")) {
                answer.add(path);
            }
        }
        return answer;
    }
}

import (
    "sort"
    "strings"
)

func removeSubfolders(folder []string) []string {
    sort.Strings(folder)
    answer := make([]string, 0, len(folder))
    for _, path := range folder {
        if len(answer) == 0 ||
            !strings.HasPrefix(path, answer[len(answer)-1]+"/") {
            answer = append(answer, path)
        }
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(nL log n)$，其中 $L$ 是路径平均长度；排序比较和前缀判断都可能扫描路径字符。
  • 空间复杂度：$O(n)$（返回结果不计时，额外空间主要取决于排序实现）。

关键点总结

  • 排序把「在所有路径中找祖先」变成了「只看最后一个保留路径」。
  • 判断目录包含关系必须带上 / 边界，不能只做字符串前缀判断。
  • 子目录被跳过后不能成为新基准，最后一个保留路径才是当前有效祖先。
  • 题目是离线一次处理，排序比 Trie 更短；若需要持续插入并在线查询，再考虑 Trie。
  • 面试时要证明两件事：父目录先出现、其子目录在字典序中连续。只有证明这两点，比较答案末尾才有依据。

易错点总结

  • 未排序就扫描：子目录可能先于父目录出现，无法被过滤。
  • 只判断 startsWith(parent)：会把 /ab 错当成 /a 的子目录。
  • 与上一条输入而非上一条保留路径比较：被过滤项会遮住真正的祖先。
  • 跳过子目录时仍更新基准：后续同父目录的兄弟路径可能被错误保留。
  • 按路径长度排序：长度不能保证同一父目录的后代连续，局部比较失去正确性。

相似题目

题目 难度 考察点
14. 最长公共前缀 简单 排序后只比首尾两串即可确定公共前缀
208. 实现 Trie (前缀树) 中等 把前缀关系显式建成树，支持在线插入与查询
648. 单词替换 中等 在词根集合中找最短匹配前缀，需要按长度取优先
720. 词典中最长的单词 中等 要求每个前缀都在词典中，排序后逐层扩展