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）」的数据结构来高效地识别和去除子文件夹，通过前缀树来构建文件夹结构，然后根据构建的树来输出没有子文件夹的路径。

1. 构建前缀树：遍历文件夹列表 folder，将每个路径插入前缀树。若发现一个路径的父节点已经被标记为叶子节点，则跳过该路径，因为它是一个子文件夹。
2. 标记叶子节点：在插入每个文件夹路径时，如果某路径成为叶子节点，表示它是当前的最上级父文件夹，可以清除这个路径的其他子文件夹路径。
3. 遍历前缀树，提取文件夹路径：深度优先遍历前缀树，通过前缀树中的叶子节点获取所有没有子文件夹的父文件夹路径。

这种方法的优点是直接在构建过程中判断和过滤子文件夹，避免了排序操作；缺点是构造前缀树结构稍显复杂，但它在文件夹路径较长或排序操作成本较高时具有更优的性能。

复杂度分析

• 时间复杂度：O(n * m)，其中 n 是文件夹数量，m 是每个文件夹路径的平均长度。
• 空间复杂度：O(n * m)，构建前缀树需要 O(n * m) 的空间。

思路二：排序

1. 首先对 folder 数组进行字典顺序排序（也就是通常的字符串排序），这样可以确保如果某个文件夹是其他文件夹的子文件夹，那么父文件夹必然会在子文件夹之前。

2. 遍历排序后的文件夹列表，筛选出父文件夹：

   • 初始化一个结果数组 res，一个 lastPath 参数用于记录上一个路径。
   • 开始逐个检查每个路径 path 是否为 lastPath 的子文件夹，判断方法是：path.startsWith(lastPath + '/')。
   • 如果 path 不是 lastPath 的子文件夹，则将其添加到 res 中，并更新 lastPath 为 path。

3. 经过上述筛选，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;
};