删除子文件夹 图解题解
这道题到底在问什么
- 输入
- folder=[/a, /a/b, /c/d, /c/d/e, /c/f]
- 输出
- [/a, /c/d, /c/f]
- 输入
- folder=[/a, /ab, /a/b]
- 输出
- [/a, /ab]（/ab 不是 /a 的子目录）
最优解：一步一步想明白
- 3记住「排序让父在子前 → 只和上一个保留项比 + 斜杠前缀」。那个斜杠是关键:它把 /a/b(子目录)和 /ab(同级别的另一个目录)区分开。
- 4先看原始输入:[/c/d, /a, /a/b, /c/d/e, /ab],顺序是乱的,/a 和它的子目录 /a/b 没挨着。直接两两比会很费劲。
- 5第一步先按字典序排序。字典序里,前缀更短的字符串排在前,所以每个父目录都会落到它子目录的前面。
- 6按字典序排序,得到 [/a, /a/b, /ab, /c/d, /c/d/e]。注意 /a 排在 /a/b 前、/c/d 排在 /c/d/e 前——父一定在子之前,这正是后面只比「上一个保留项」就够的底气。
- 7结果列表 ans 先清空。接下来从左往右扫每个路径,只和 ans 里最后一个保留项比。
- 8轮到第 0 个 /a(紫)。此刻 ans 还是空的,没有可比的保留项。
- 9先看 ans:还是空的,没有上一个保留项可比,那它直接就该留下。
- 10ans 是空的,/a 当然要保留(标绿),它成为新的「上一个保留项」。
- 11轮到第 1 个 /a/b(紫)。ans 里最后一个保留项是 /a(蓝),拿它来比。
- 12把 /a/b 和「/a/」(上一个保留项 /a 再加个斜杠)逐字符比一比,看它是不是以这个前缀开头。
- 13判定:/a/b 以「/a/」开头(连斜杠一起),说明它就在 /a 这个目录里面,是子文件夹,跳过(标灰),不进 ans。
- 14轮到第 2 个 /ab(紫)。ans 里最后一个保留项是 /a(蓝),拿它来比。
- 15把 /ab 和「/a/」(上一个保留项 /a 再加个斜杠)逐字符比一比,看它是不是以这个前缀开头。
- 16判定:/ab 虽然也以 /a 这几个字打头,但下一个字符不是斜杠(是「b」),所以它不是 /a 的子目录,而是另一个目录,保留(标绿)。这就是那个斜杠的作用。
- 17轮到第 3 个 /c/d(紫)。ans 里最后一个保留项是 /ab(蓝),拿它来比。
- 18把 /c/d 和「/ab/」(上一个保留项 /ab 再加个斜杠)逐字符比一比,看它是不是以这个前缀开头。
- 19判定:/c/d 不以「/ab/」开头,它是个新的目录,保留(标绿),成为新的「上一个保留项」。
- 20轮到第 4 个 /c/d/e(紫)。ans 里最后一个保留项是 /c/d(蓝),拿它来比。
- 21把 /c/d/e 和「/c/d/」(上一个保留项 /c/d 再加个斜杠)逐字符比一比,看它是不是以这个前缀开头。
- 22判定:/c/d/e 以「/c/d/」开头(连斜杠一起),说明它就在 /c/d 这个目录里面,是子文件夹,跳过(标灰),不进 ans。
- 23扫完全程:绿色 [/a, /ab, /c/d] 是保留下来的,灰色 /a/b、/c/d/e 是被删的子文件夹。回头看,排序加一遍扫描就搞定,关键全在「排序让父在子前」和那个分隔斜杠。
- 24再回顾一遍:排序让每个父目录排到子目录前,于是扫描时只需拿当前路径和「上一个保留项 + 斜杠」做一次前缀判断,就能定出它是不是子文件夹,省掉了和所有保留项逐个比较。绿色 [/a, /ab, /c/d] 即答案。
⚠️ 容易写错的地方
✗ 错：判前缀时漏掉那个斜杠
✓ 对：判「last + 斜杠」开头,不是只判 last 开头
只判 last 开头会把 /ab 误当成 /a 的子目录;加上斜杠才能区分 /a/b(子)和 /ab(非子)
✗ 错：不排序就两两比较
✓ 对：先排序让父排在子前
排序后父一定在子前,只比上一个保留项即可,不必两两 O(n²) 比
✗ 错：和 ans 里所有项都比一遍
✓ 对：只和最后一个保留项比
排序后,能成为某项父目录的只可能是紧邻它前面的那个保留项,比全部是多余的
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def removeSubfolders(self, folder: List[str]) -> List[str]:
folder.sort()
ans = []
for path in folder:
if not ans or not path.startswith(ans[-1] + '/'):
ans.append(path)
return ansC++
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
vector<string> removeSubfolders(vector<string>& folder) {
sort(folder.begin(), folder.end());
vector<string> ans;
for (auto &path : folder) {
if (ans.empty() || path.rfind(ans.back() + "/", 0) != 0) ans.push_back(path);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public List<String> removeSubfolders(String[] folder) {
Arrays.sort(folder);
List<String> ans = new ArrayList<>();
for (String path : folder) {
if (ans.isEmpty() || !path.startsWith(ans.get(ans.size() - 1) + "/")) ans.add(path);
}
return ans;
}
}复杂度
时间
O(L·n·log n)
排序是 n·log n 次比较、每次比较最坏要看 L 个字符(L 为路径平均长度);再加一遍扫描、每次前缀判定 O(L)
空间
O(L·n)
结果列表与排序所需空间,数量级是所有路径的总字符数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 删除子文件夹 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
不排序能不能做?+
能,用字典树(Trie):把每个路径按「/」切成若干段,逐段插入 Trie;插入时如果中途经过了一个「已经是某条完整路径终点」的节点,说明当前路径是它的子文件夹,丢弃。这样不需要排序,复杂度是总字符数级别。排序法更短好写,Trie 法在路径极多时更稳。
为什么排序能保证父在子前?+
父目录是子目录的前缀(比如 /a 是 /a/b 的前缀),而字典序里,一个字符串排在它的任何扩展串前面(前缀更短、在比较到结尾时先结束),所以父一定排在子前。这条性质正是排序法成立的根。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 删除子文件夹 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。