1233. 删除子文件夹

题目链接：1233. 删除子文件夹

方法一：排序 + 循环

解题思路

先对 \(folder\) 数组根据字典序进行排序，排序完成后，扫描 \(folder\) 数组。由于在同一个高层目录下的文件夹在同一段区域，那么这一段区域的第一个文件夹就是这一系列文件夹的最高层目录 \((high)\)，将其加入结果数组中。当出现以下情况之一时，表明扫描到下一区域：

• 当前文件名长度 \(< high.size()\) 时，因为子文件夹名长度一定大于其高层文件夹名；
• \(high\) 不是当前文件夹名的前缀；
• 当前文件夹名的第 \(high.size()\)（从 \(0\) 开始）个字符 != '/'，一定不是其子文件夹。

代码

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        sort(folder.begin(), folder.end());
        vector<string> ans{folder[0]};
        for (int i = 1; i < folder.size(); i ++ ) {
            int pre = (*ans.rbegin()).size();
            if (pre >= folder[i].size() || *ans.rbegin() != folder[i].substr(0, pre) || folder[i][pre] != '/') ans.emplace_back(folder[i]);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(nlogn)\)；
空间复杂度：\(O(1)\)。

方法二：字典树

解题思路

参考-JDFZ 2019级 蒟蒻OIer：字典树(Trie)详解

代码

class Trie {
private:
    unordered_map<string, Trie*> children;
    int fid = -1; // fid != -1时，表示此节点为某字符串的终点，存储当前字符串在folder中的idx，方便取出整个字符串

public:
    vector<string> split(string &str) { // 将str中'/'去掉，将str分为一个个节点
        vector<string> res;
        int len = str.length();
        int l = 1, r = str.find_first_of('/', l); // 从idx=l开始，查询'/'下标
        while (r != string::npos) {
            res.push_back(str.substr(l, r - l));
            l = r + 1;
            r = str.find_first_of('/', l);
        }
        res.push_back(str.substr(l));
        return res;
    }

    void insert(int fid, string &str) {
        Trie* node = this; // 方便后续节点插入操作
        vector<string> ps = split(str);
        for (auto &c : ps) {
            if (!node->children.count(c)) { // 该子节点未被加入到trie中
                node->children[c] = new Trie();
            }
            node = node->children[c]; // 变更父节点，从而插入下一个节点
        }
        node->fid = fid; // 到达该字符串终点，设置fid
    }

    vector<string> search(vector<string>& folder) {
        vector<string> ans;
        function<void(Trie*)> dfs = [&](Trie* root) { //function<>特性 + lambda表达式
            if (root->fid != -1) { // 到达该分支第一个字符串终点，后面为该文件目录的子文件夹
                ans.push_back(folder[root->fid]);
                return;
            }
            for (auto& [str, child] : root->children) dfs(child);
        };
        dfs(this);
        return ans;
    }
};

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        Trie* trie = new Trie();
        for (int i = 0; i < folder.size(); i ++ ) {
            trie->insert(i, folder[i]);
        }
        return trie->search(folder);
    }
};

复杂度分析

时间复杂度：\(O(n * m)，n = folder.length()，m = max(folder[0...n-1].length())\)；
空间复杂度：\(O(n * m)\)。