Leetcode.1233 删除子文件夹

题目链接

Leetcode.1233 删除子文件夹 Rating : 1545

题目描述

你是一位系统管理员手里有一份文件夹列表 folder你的任务是要删除该列表中的所有 子文件夹并以 任意顺序 返回剩下的文件夹。

如果文件夹folder[i]位于另一个文件夹 folder[j]下那么folder[i]就是folder[j] 的 子文件夹 。

文件夹的「路径」是由一个或多个按以下格式串联形成的字符串'/' 后跟一个或者多个小写英文字母。

例如"/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\ast 10^4$
• $2<=folder[i].length<=100$
• folder[i]只包含小写字母和 '/'
• folder[i]总是以字符 '/'起始
• 每个文件夹名都是 唯一 的

分析

先对 folder排序因为 字典序小的 才可能包含 字典序大的 文件夹。

例如排序之后 [/a,/a/b,/a/b/c,/a/b/d]。用一个 prev记录前一个父文件夹prev能够匹配当前子串 s则说明 s是 prev的子文件夹直接跳过本次循环。否则更新 prev。

时间复杂度$O(n\ast logn\ast m)$

C++代码

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        vector<string> res;
        sort(folder.begin(),folder.end());

        string prev = "";
        for(auto f:folder){
            if(prev != "" && f.find(prev) == 0) continue;
            //加 '/' 是为了防止出现以下 识别为相同的情况
            //    /a/b/c    /a/b/ca
            prev = f + "/";
            res.push_back(f);
        }

        return res;
    }
};

Java代码

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        vector<string> res;
        sort(folder.begin(),folder.end());

        string prev = "";
        for(auto f:folder){
            if(prev != "" && f.find(prev) == 0) continue;
            prev = f + "/";
            res.push_back(f);
        }

        return res;
    }
};