---

1233. 删除子文件夹

• 标签：字典树、数组、字符串
• 难度：中等

题目链接

• 1233. 删除子文件夹 - 力扣

题目大意

描述：给定一个文件夹列表 $folder$，其中每个路径都使用 Unix 风格（即 / 分隔），且所有路径都是唯一的。

要求：删除所有子文件夹。如果文件夹 $A$ 是文件夹 $B$ 的子文件夹（即 $A$ 的路径以 $B$ 的路径开头，且 $B$ 路径后面紧跟一个 /），则删除 $A$。返回剩余的文件夹列表。

说明：

• $1 \le folder.length \le 4 \times 10^{4}$。
• $2 \le folder[i].length \le 100$。
• $folder[i]$ 只包含小写字母和 /。

示例：

• 示例 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：

输入：folder = ["/a","/a/b/c","/a/b/d"]
输出：["/a"]
解释："/a/b/c" 和 "/a/b/d" 都是 "/a" 的子文件夹。

• 示例 3：

输入：folder = ["/a/b/c","/a/b/ca","/a/b/d"]
输出：["/a/b/c","/a/b/ca","/a/b/d"]
解释："/a/b/ca" 不是 "/a/b/c" 的子文件夹，因为 "c" 后没有紧跟 "/"。

解题思路

思路 1：排序 + 前缀判断

1. 核心思想

将 $folder$ 按字典序排序。排序后，如果一个文件夹是另一个的子文件夹，它们一定相邻或邻近。

具体来说：排序后，如果 $folder[i]$ 以 $folder[j]$ 开头且 $folder[j]$ 后面紧跟着 /，那么 $folder[i]$ 是 $folder[j]$ 的子文件夹。

2. 具体步骤

第 1 步：对 $folder$ 按字典序排序。

第 2 步：遍历排序后的 $folder$：

• 用 $ans$ 存储结果，初始时第一个文件夹加入 $ans$。
• 对于当前文件夹 $cur$，检查它是否以 $ans[-1]$ 为前缀，并且 $cur$ 在 $ans[-1]$ 后面紧跟 /。
• 如果是，说明 $cur$ 是子文件夹，跳过。
• 如果不是，说明 $cur$ 是新的父文件夹，加入 $ans$。

第 3 步：返回 $ans$。

3. 为什么排序后这样检查是正确的？

排序后，所有以 /a 开头的文件夹会排在一起，而以 /a 为前缀的最短路径（即 /a 本身，如果存在）会出现在最前面。所以用 $ans$ 中最后一个"已确认的父文件夹"来检查即可。

4. 结合示例走一遍

$folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]$

排序后：$["/a","/a/b","/c/d","/c/d/e","/c/f"]$

• "/a" → $ans=["/a"]$
• "/a/b" → 以 "/a/" 开头 → 子文件夹，跳过
• "/c/d" → 不以 "/a/" 开头 → 新父文件夹，$ans=["/a","/c/d"]$
• "/c/d/e" → 以 "/c/d/" 开头 → 子文件夹，跳过
• "/c/f" → 不以 "/c/d/" 开头 → 新父文件夹，$ans=["/a","/c/d","/c/f"]$

思路 1：代码

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        ans = [folder[0]]
        for i in range(1, len(folder)):
            # 检查当前文件夹是否以 ans[-1] 为前缀
            prev = ans[-1]
            cur = folder[i]
            # 注意要加 "/" 避免误判，如 "/a/b/ca" 不以 "/a/b/c/" 开头
            if not (len(cur) > len(prev) and cur[:len(prev) + 1] == prev + '/'):
                ans.append(cur)
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n \log n \times L)$，其中 $n$ 是文件夹数量，$L$ 是文件夹路径的平均长度。排序需要 $O(n \log n)$ 时间，比较前缀需要 $O(L)$ 时间。
• 空间复杂度：$O(1)$，不考虑存储结果所需的空间。

思路 2：字典树

1. 核心思想

用字典树（Trie）存储所有路径。每个节点表示一个目录名。DFS 遍历字典树，遇到的第一个完整路径节点就是父文件夹，它的所有子节点都是子文件夹，不需要加入结果。

但思路 1 更简洁高效，思路 2 的实现更复杂但更灵活（例如可以处理更复杂的文件系统查询）。