题目链接：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)\)。