删除子文件夹(LeetCode 1233)的解法
答案要点
- 按字典序排序后,父文件夹必然排在子文件夹之前,子孙紧随其后
- 只与最后一个保留的路径比较,判断是否以「该路径 + /」为前缀
- 前缀判断必须带斜杠,区分 /a/b 与 /a/bc 这种同前缀但不是父子的情况
- 排序法 O(n·L·log n);Trie 按路径分段插入并在结尾标记,DFS 遇标记即剪枝,近似线性
- 哈希集合法:对每个路径在每个斜杠处截前缀查集合,命中就说明是子文件夹
易错点
- 前缀判断不加斜杠,把 /a/bc 当成 /a/b 的子文件夹
- 每次都和所有已保留路径比较,退化成 O(n^2·L)
- 哈希集合法直接截取每个字符前缀而不是在斜杠处截取,会产生误判
面试官常见追问
- 为什么只和最后一个保留的路径比,不用和所有保留路径比?
- Trie 方案具体怎么写?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 数组和链表的区别与适用场景173 场
- 经典算法题:最长回文子串、无重复最长子串、最大子数组和141 场
- 合并有序数组与合并区间66 场
- 三数之和:排序加双指针50 场
- 字符串相加(大数加法)20 场
- 字符串匹配:KMP 算法18 场
- 字符串反转的实现与注意事项17 场
- 接雨水问题的三种解法14 场
- 螺旋矩阵遍历14 场
- 两数之和的几种解法12 场