删除子文件夹

标签: 深度优先搜索 字典树 数组 字符串

难度: Medium

你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。

如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。

文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：'/' 后跟一个或者多个小写英文字母。

  • 例如，"/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 * 104
  • 2 <= folder[i].length <= 100
  • folder[i] 只包含小写字母和 '/'
  • folder[i] 总是以字符 '/' 起始
  • folder 每个元素都是 唯一 的

Submission

运行时间: 52 ms

内存: 29.8 MB

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        res = []
        parent = ''
        ind = 2
        for f in folder:
            if f[:ind] != parent:
                ind, parent = len(f) + 1, f + '/'
                res.append(f)
        return res

Explain

首先对文件夹列表进行排序，以确保任何文件夹都会在其可能的子文件夹之前出现。然后，初始化一个空结果列表以及一个表示当前父文件夹的变量。遍历排序后的文件夹路径，对于每个路径，检查它是否以当前父文件夹为前缀。如果不是，更新当前的父文件夹并将其加入结果列表。这样可以确保只有最顶级的文件夹被加入到结果中，因为一旦一个文件夹被认定为父文件夹，所有的子文件夹（由于字符串排序的特性，子文件夹会紧随其后）都会被忽略。

时间复杂度: O(n log n + nm)

空间复杂度: O(n)

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()  # 对文件夹路径进行排序
        res = []  # 初始化结果列表
        parent = ''  # 初始化父文件夹路径为空字符串
        ind = 2  # 初始化父文件夹长度的下一个索引
        for f in folder:  # 遍历每个文件夹
            if f[:ind] != parent:  # 如果当前文件夹不是子文件夹
                ind, parent = len(f) + 1, f + '/'  # 更新父文件夹和长度索引
                res.append(f)  # 将当前文件夹加入到结果列表
        return res  # 返回结果列表

Explore

在检查当前文件夹是否为某个已确定的父文件夹的子文件夹时，添加'/'是为了确保精确匹配文件夹的边界。例如，如果父文件夹是'/a/b'，而当前文件夹是'/a/bc'，仅仅比较前缀'/a/b'会错误地认为'/a/bc'是'/a/b'的子文件夹。添加'/'变成'/a/b/'后，'/a/bc'就不会被认为是子文件夹，因为它不匹配前缀'/a/b/'。这样可以避免错误地将两个实际上是平级关系的文件夹处理为父子关系。

初始化`ind`为2的具体原因可能是误解或错误。在上下文中，`ind`应该是表示父文件夹路径长度加1的索引，用于确保子文件夹比较时的正确性。理论上，`ind`应该初始化为一个与路径无关的值，或在逻辑中根据首个文件夹路径在循环开始时设置。这里将`ind`初始化为2没有明确的逻辑依据，可能是代码书写上的疏忽。

通过对文件夹路径进行字典序排序，可以确保每个文件夹都会在其可能的任何子文件夹之前出现。字典序排序意味着字符串是按照字符顺序逐个比较的，这自然地将较短的或者在字典序中较早的路径排在前面。这种排序方式已经考虑了包括文件夹名称相似但不同的情况，例如'/a'会排在'/a/b'之前。这确保了在处理时能够按照父文件夹到子文件夹的顺序进行正确处理。

如果输入的文件夹列表中包含重复的路径，这个算法依然可以正确地处理。由于每个文件夹只有在不是之前文件夹的子文件夹时才被添加到结果列表中，重复的路径会在第一次出现时被添加到结果列表，之后的重复项由于与当前父文件夹完全相同，不会再次被添加。因此，结果列表中不会包含重复的文件夹路径。