LeetCode 1233. 删除子文件夹
题目描述
题意分析
如果一条路径是列表中另一条路径的子文件夹，就将它删除。最终保留的路径不能再有出现在列表中的祖先；路径中有多级目录，并不代表它一定会被删除。
子文件夹关系必须跨过完整的目录边界：当前路径要以“父路径 +
/”开头，单纯的字符串前缀相同不够。结果顺序不限，因此可以先排序；下面的实现会修改输入数组的顺序。
解法：字典序排序后过滤
核心思路
[!blue]
按字典序排序后，父路径一定先于它的子文件夹出现，带有同一个“父路径 +
/”前缀的后代也会集中在一起。这样就可以把两两比较转成一次从左到右的扫描。用答案列表的最后一项作为当前保留的父路径。若当前路径以它加
/为前缀，说明当前路径已经被覆盖，直接跳过；否则当前路径应当保留，并成为新的比较基准。只检查最后保留的一项就够了：若当前路径属于某个更早保留的祖先，它应当出现在那个祖先对应的连续后代区域中，不会越过另一个已保留路径才出现。更早的后代区域一旦结束，后续就不可能再被它覆盖。
被删除的路径不能替换比较基准。它只代表祖先下面的某一条分支，而保留下来的祖先还可能覆盖后面的其他分支。
解题步骤
- 将
folder按字典序升序排列，建立空的答案列表。- 依次读取每条路径；答案为空时直接保留第一条。
- 取答案的最后一项，拼接
/作为子目录前缀。- 当前路径匹配这个前缀时跳过，不改变答案；否则追加到答案末尾。
- 扫描完成后返回答案。每条被跳过的路径都有一个保留下来的祖先。
代码实现
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)$，其中
n是路径数，L是最大路径长度。排序中一次字符串比较最多需要 $O(L)$，排序后的前缀检查总共需要 $O(nL)$。- 空间复杂度：$O(n+L)$ 上界，计入结果列表、排序辅助空间和拼接的临时前缀字符串。结果直接保存原路径，不需要复制每条路径的内容。
关键点总结
[!green]
- 字典序让父路径先出现，并把它能覆盖的后代集中在一个连续范围。
- 比较对象是最后保留的路径，它始终代表当前仍可能覆盖后续路径的祖先。
- 匹配“路径 +
/”才能判断目录包含关系。
易错点总结
[!yellow]
- 不能只判断字符串前缀，父路径之后必须紧跟目录分隔符。
- 不要与原数组的上一项比较；上一项可能已经被删除，不能代表真正覆盖当前路径的祖先。
- 仅按路径长度排序不能保证后代集中出现，此时只比较一个基准不再成立。
- 题目保证路径互不相同，且不存在单独的根路径
/；算法按这些路径格式直接判断前缀即可。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1166. 设计文件系统 | 中等 | 按路径组件建立树或Trie后，遇到保留的父目录即可忽略其全部后代。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！