1233. Remove Sub-Folders from the Filesystem
1233. Remove Sub-Folders from the Filesystem
给一系列目录字符串,要求只返回父目录
排序再去除 O(nlogN)
排序之后,可能为父子目录关系的目录便会在一起且第一个肯定为父目录,通过比对字符串前缀是否相等来去重
将层级问题通过排序简化为线性问题,避免了构建层级结构的空间使用
class Solution {
public:
vector<string> removeSubfolders(vector<string>& folder) {
sort(folder.begin(), folder.end());
vector<string> res;
res.push_back(folder[0]);
for(int i=1;i<folder.size();++i) {
string s = res.back()+"/";
if (folder[i].substr(0, s.size())!=s) {
res.push_back(folder[i]);
}
}
return res;
}
};#string