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