菜单
文章 Leetcode

1233. 删除子文件夹

beautifulremi

beautifulremi

• 阅读本文需 12 分钟

题目

你是一位系统管理员，手里有一份文件夹列表 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 * 104
  • 2 <= folder[i].length <= 100
  • folder[i] 只包含小写字母和 '/'
  • folder[i] 总是以字符 '/' 起始
  • folder 每个元素都是 唯一 的

解题思路

核心是找出所有“顶级”文件夹，并删除掉它们的任何“子文件夹”。关键在于如何高效地识别出这种父子关系。我们观察这道题可以找到题干中有两个值得注意的点：

  • 子文件夹的定义：如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。
  • 输出的要求：可以以 任意顺序 返回剩下的文件夹。

根据这两个要点，我们有一个直观的思路就是维护一个集合，对每个文件夹在这个集合中寻找这个文件夹可能的父文件夹是否存在，如果存在父文件夹就不添加进这个集合，如果不存在就把这个文件夹添加进这个集合作为父文件夹。

但是很快我们会发现一个问题，假设我们有 /a 和 /a/b，那么如果 /a/b 先被读取，此时 /a 还没有被读取，我们就会错误地将 /a/b 录入，而且在一次录入中没有任何的检查手段。因此，如果我们想要进行有效的检查，我们必须保证在遍历集合的时候父文件夹在子文件夹的前面。

一旦意识到了这一点，我们就需要对原集合的元素顺序进行适当的改变，并且考虑到这个排序算法的时间复杂度可能很关键，我们可以预料其的平均时间复杂度不应该超过 O(NlogN)。此时我们的基本思路便是先排序，再遍历。

排序法

具体思路

这个方法的思路很自然，如果我们要对集合进行重新排序，升序排序是恰好满足要求的。此时所有文件夹路径按照字典序（也就是字母顺序）进行排序。我们排序后的结果中，路径结构相似的文件夹会恰好聚集在一起。并且，一个父文件夹（如 "/a"）一定会排在它的所有子文件夹（如 "/a/b", "/a/b/c"）之前。

例如，原始列表：["/c/d", "/a", "/a/b", "/c/f", "/c/d/e"] 排序后变为：["/a", "/a/b", "/c/d", "/c/d/e", "/c/f"]

因此，接下来我们只需要进行遍历和比较即可，此时比起维护一个具体的表，因为升序排序把文件夹都聚集在一起，我们可以直接遵循题干给出的定义，具体的思路是：

  • 创建一个空的列表 result 用来存放最终结果。
  • 将排序后列表中的第一个文件夹直接加入 result。它一定是顶级文件夹之一。
  • 从排序后列表的第二个文件夹开始遍历，将当前文件夹与 result 列表中的最后一个文件夹进行比较。我们需要检查 current 是否是 parent 的子文件夹。根据题意，current 是 parent 的子文件夹的充要条件是：current 字符串以 parent + "/" 开头。
    • 设 result 中最后一个文件夹为 parent。
    • 设当前遍历到的文件夹为 current。
    • 如果不是子文件夹：说明 current 是一个新的顶级文件夹。将 current 添加到 result 列表中。

代码实现

#include<algorithm>
#include<iterator>
#include<vector>
#include<string>

using namespace std;

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        sort(folder.begin(), folder.end()); //升序排列
        vector<string> result;
        result.push_back(folder[0]); //第一个一定不是子文件夹
        for(auto iter = (folder.begin() + 1); iter < folder.end(); iter++) 
        // 从第二个开始检查和result里最后一个元素的关系
        {
            string current = *iter;
            string parent = *(result.back());
            string prefix = parent + "/";
            if(current.find(prefix) != 0)
            {
                result.push_back(*iter);
            }
        }

        return result;
    }
};

时间复杂度

  • N：文件夹的总数量 (folder.size())。
  • L：文件夹路径的平均长度。

总的时间开销主要由两部分组成：排序和遍历。

排序开销: O(NlogN⋅L)

  • C++ 的 sort 使用内省排序，平均和最坏情况下的时间复杂度都是 O(NlogN) 次比较操作。
  • 关键：我们排序的对象是字符串 (string)。比较两个字符串的开销并不是 O(1)，而是与它们的长度成正比。在最坏情况下，比较两个长度为 L 的字符串需要 O(L) 的时间。
  • 因此，排序的总时间复杂度是 O(NlogN⋅L)。

遍历开销: O(N⋅L)

  • 排序之后，你需要一个 for 循环来遍历这 N 个文件夹（严格来说是 N−1 个，但数量级是 N）。
  • 在循环的每一步中，主要操作有：
    • result.back(): 获取 vector 最后一个元素，这是 O(1) 操作。
    • string prefix = parent + "/";: 创建一个新的前缀字符串。这个操作需要复制 parent 字符串并添加一个字符，其开销与 parent 的长度成正比，即 O(L)。
    • current.find(prefix): 检查前缀。这个操作的开销也与前缀的长度成正比，即 O(L)。
    • result.push_back(): 将一个字符串添加到结果中。这涉及到一次字符串拷贝，开销也是 O(L)。
  • 综上，循环中每一步的开销大约是 O(L)。因为循环要执行 N 次，所以这部分的总时间复杂度是 O(N⋅L)。

总时间复杂度 = 排序开销 + 遍历开销 T(N)=O(NlogN⋅L)+O(N⋅L)，最终时间复杂度为 O(NlogN⋅L)。

哈希表法

具体思路

因为注意到题目中的要求是"可以以 任意顺序 返回剩下的文件夹"，而满足这个性质的数据结构我们往往会想到哈希表。因为哈希表中增删改查的时间复杂度都是 O(1) ，因此即使是按之前的排序法，在之后使用哈希表存储相关数据理论上第二步的时间也会增快很多。

在此之上，我们可以构思出进一步的优化方法，因为我们已经打算以哈希表存储了，那么原来的字典序排序中的文件夹成簇分布性质已经不再需要了，这个地方是可以进行优化了。我们已知进行重新排序这个操作不管如何一定是要占用 O(NlogN) 的时间复杂度的，那么整个算法中另外最耗时间的操作实际上就在字符串的比较上。比较两个字符串需要逐个字符地进行，直到发现不同之处。那么对于两个平均长度为 L 的字符串，单次比较操作的平均时间复杂度是 O(L)。

但实际上，如果我们只要求父文件夹在子文件夹前，我们只需要比较长度即可，因为子文件夹的长度是一定大于其对应的父文件夹的，不管其对应的父文件夹有多少个。而长度这个属性是一维的，也只需要在 O(1) 的时间复杂度内完成。

因此我们的思路已经很清晰了，sort 只需要比较两个字符串的长度，即 a.size() < b.size()，获取 string 的长度是一个 O(1) 操作，因为长度信息是直接存储的。这意味着单次比较几乎是瞬时的。总的排序时间复杂度就是 O(NlogN)。这对结果的速度平均上也可以得到50倍的加速。

在排序后，我们需要维护两个数据结构：

  • unordered_set<ULL> rootFolderHashes：一个哈希表，用来存放所有已被确认为根目录的文件夹的“组合哈希值”。目的是以 O(1) 的速度查询某个路径是否是已知的根目录。
  • vector<string> rootFolders：一个动态数组。它用来存放最终结果，即那些通过了所有检查的、非子文件夹的原始字符串。

接着对所有排序好的结果进行遍历，具体来说：

  1. 前缀检查：对于当前处理的文件夹，算法会迭代生成它的所有有效父路径前缀（即以 / 分隔的、比自身短的前缀）。对每一个生成的前缀，它会计算出对应的哈希值。
  2. 状态查询：它使用上一步计算出的前缀哈希值，去哈希集合（rootFolderHashes）中查询。
  3. 筛选决策：
    • 如果查询命中（即在集合中找到了该前缀的哈希值），则证明当前文件夹是一个已知根目录的子文件夹。算法会立即停止对该文件夹的进一步检查，并将其丢弃。
    • 如果查询未命中（即检查完所有父路径前缀，它们的哈希值都不在集合中），则证明该文件夹不是任何已知根目录的子文件夹，它本身是一个新的根目录。
  4. 状态更新：对于被确定为新根目录的文件夹，算法会将其完整的哈希值添加到哈希集合中，以备后续更长的文件夹进行检查；同时，将其原始字符串添加到最终的结果列表中。

最终的列表中留下的就是所有符合要求的结果。

代码实现

#include <algorithm>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        // 增加对空输入的处理
        if (folder.empty()) {
            return {};
        }

        // 双哈希，提升稳健性
        using ULL = unsigned long long;
        const int P1 = 911, P2 = 131; // 使用两个不同的质数

        // 按字符串长度从小到大排序
        sort(folder.begin(), folder.end(), [](const string& a, const string& b) {
            return a.size() < b.size();
        });

        // 存储根目录的哈希对
        unordered_set<ULL> rootFolderHashes;
        vector<string> rootFolders;

        for (const string& path : folder) {
            bool isSubfolder = false;
            ULL hash1 = 0, hash2 = 0;

            for (int i = 0; i < path.size() - 1; ++i) {
                hash1 = hash1 * P1 + path[i];
                hash2 = hash2 * P2 + path[i];

                // 如果下一个字符是'/'，说明形成了一个父路径，进行检查
                if (path[i + 1] == '/') {
                    // 将两个哈希值合并成一个，存入集合
                    ULL combinedHash = (hash1 << 32) | hash2;
                    if (rootFolderHashes.count(combinedHash)) {
                        isSubfolder = true;
                        break;
                    }
                }
            }

            // 如果遍历完所有父路径都不是子文件夹
            if (!isSubfolder) {
                // 计算当前路径完整的哈希值
                ULL fullHash1 = 0, fullHash2 = 0;
                for(char c : path) {
                    fullHash1 = fullHash1 * P1 + c;
                    fullHash2 = fullHash2 * P2 + c;
                }
                
                ULL fullCombinedHash = (fullHash1 << 32) | fullHash2;
                rootFolderHashes.insert(fullCombinedHash);
                rootFolders.push_back(path);
            }
        }
        return rootFolders;
    }
};

时间复杂度

  • 排序：按长度比较是 O(1) 的操作，所以排序的总时间是 O(NlogN)。
  • 遍历和哈希：因为利用了滚动哈希，因此遍历所有文件夹并计算哈希值的总时间与总字符数成正比，即 O(L_total​)。哈希集合的查找和插入平均是 O(1)。
  • 这个算法的总时间复杂度是 O(NlogN+L_total​)。

注：本题有在理论上更加快的字典树法，其时间复杂度是 O(L_total)，在一次遍历中把整颗字典树构造出来，但节省时间复杂度的结果是实现复杂度的升高，并且在百万级的量级之前，因为哈希表法的单元操作更简单，往往能达到比字典树还快速的效果。

分享