1233. 删除子文件夹
1233. 删除子文件夹
🟠 🔖 深度优先搜索
字典树
数组
字符串
🔗 力扣
LeetCode
题目
Given a list of folders folder
, return the folders after removing allsub- folders in those folders. You may return the answer in any order.
If a folder[i]
is located within another folder[j]
, it is called a sub- folder of it. A sub-folder of folder[j]
must start with folder[j]
, followed by a "/"
. For example, "/a/b"
is a sub-folder of "/a"
, but "/b"
is not a sub-folder of "/a/b/c"
.
The format of a path is one or more concatenated strings of the form: '/'
followed by one or more lowercase English letters.
- For example,
"/leetcode"
and"/leetcode/problems"
are valid paths while an empty string and"/"
are not.
Example 1:
Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.
Example 2:
Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d" will be removed because they are subfolders of "/a".
Example 3:
Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]
Constraints:
1 <= folder.length <= 4 * 10^4
2 <= folder[i].length <= 100
folder[i]
contains only lowercase letters and'/'
.folder[i]
always starts with the character'/'
.- Each folder name is unique.
题目大意
你是一位系统管理员,手里有一份文件夹列表 folder
,你的任务是要删除该列表中的所有 子文件夹 ,并以 任意顺序 返回剩下的文件夹。
如果文件夹 folder[i]
位于另一个文件夹 folder[j]
下,那么 folder[i]
就是 folder[j]
的 子文件夹 。folder[j]
的子文件夹必须以 folder[j]
开头,后跟一个 "/"
。例如,"/a/b"
是 "/a"
的一个子文件夹,但 "/b"
不是 "/a/b/c"
的一个子文件夹。
文件夹的「路径」是由一个或多个按以下格式串联形成的字符串:'/' 后跟一个或者多个小写英文字母。
- 例如,
"/leetcode"
和"/leetcode/problems"
都是有效的路径,而空字符串和"/"
不是。
示例 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"]
提示:
1 <= folder.length <= 4 * 10^4
2 <= folder[i].length <= 100
folder[i]
只包含小写字母和'/'
folder[i]
总是以字符'/'
起始folder
每个元素都是 唯一 的
解题思路
思路一:前缀树
可以利用「前缀树(Trie)」的数据结构来高效地识别和去除子文件夹,通过前缀树来构建文件夹结构,然后根据构建的树来输出没有子文件夹的路径。
- 构建前缀树:遍历文件夹列表
folder
,将每个路径插入前缀树。若发现一个路径的父节点已经被标记为叶子节点,则跳过该路径,因为它是一个子文件夹。 - 标记叶子节点:在插入每个文件夹路径时,如果某路径成为叶子节点,表示它是当前的最上级父文件夹,可以清除这个路径的其他子文件夹路径。
- 遍历前缀树,提取文件夹路径:深度优先遍历前缀树,通过前缀树中的叶子节点获取所有没有子文件夹的父文件夹路径。
这种方法的优点是直接在构建过程中判断和过滤子文件夹,避免了排序操作;缺点是构造前缀树结构稍显复杂,但它在文件夹路径较长或排序操作成本较高时具有更优的性能。
复杂度分析
- 时间复杂度:
O(n * m)
,其中n
是文件夹数量,m
是每个文件夹路径的平均长度。 - 空间复杂度:
O(n * m)
,构建前缀树需要O(n * m)
的空间。
思路二:排序
首先对
folder
数组进行字典顺序排序(也就是通常的字符串排序),这样可以确保如果某个文件夹是其他文件夹的子文件夹,那么父文件夹必然会在子文件夹之前。遍历排序后的文件夹列表,筛选出父文件夹:
- 初始化一个结果数组
res
,一个lastPath
参数用于记录上一个路径。 - 开始逐个检查每个路径
path
是否为lastPath
的子文件夹,判断方法是:path.startsWith(lastPath + '/')
。 - 如果
path
不是lastPath
的子文件夹,则将其添加到res
中,并更新lastPath
为path
。
- 初始化一个结果数组
经过上述筛选,
res
中的每个文件夹路径都不是其他路径的子文件夹,直接返回res
作为最终结果。
复杂度分析
- 时间复杂度:
O(n log n)
,其中n
是文件夹的数量,主要开销在对folder
数组进行排序。 - 空间复杂度:
O(n)
,用于存储结果数组,最坏情况下(当所有文件夹都是独立的,没有子文件夹),res
的长度与输入数组相同。
代码
/**
* @param {string[]} folder
* @return {string[]}
*/
var removeSubfolders = function (folder) {
let tire = {};
// 将文件夹路径插入前缀树
for (let str of folder) {
let cur = tire;
for (let char of str.split('/')) {
// 如果已经是叶子节点,当前路径为子文件夹,直接 break
if (cur.isEnd == true) {
break;
}
if (!cur[char]) {
cur[char] = {};
}
cur = cur[char];
}
// 当前路径为叶子节点,清空其他子文件夹路径
Object.keys(cur).forEach((key) => delete cur[key]);
// 标记为叶子节点
cur.isEnd = true;
}
let res = [];
// 遍历前缀树,收集叶子节点路径
const backtrack = (root, track) => {
if (root.isEnd == true) {
res.push(track.join('/'));
return;
}
for (let key of Object.keys(root)) {
track.push(key);
backtrack(root[key], track);
track.pop();
}
};
backtrack(tire, []);
return res;
};
/**
* @param {string[]} folder
* @return {string[]}
*/
var removeSubfolders = function (folder) {
// 对 folder 数组进行字典顺序排序
folder.sort();
let res = [],
lastPath = '';
for (path of folder) {
// 比较 path 是不是 lastPath 的子文件夹
if (!lastPath || !path.startsWith(lastPath + '/')) {
res.push(path);
lastPath = path;
}
}
return res;
};