跳至主要內容

1233. 删除子文件夹


1233. 删除子文件夹

🟠   🔖  深度优先搜索 字典树 数组 字符串  🔗 力扣open in new window LeetCodeopen in new window

题目

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 中,并更新 lastPathpath
  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;
};