(LeetCode 每日一题) 1233. 删除子文件夹 (排序)

题目：1233. 删除子文件夹

思路：排序，时间复杂度0(L*nlogn)。

文件夹a的子文件b，b字符串字典序列一定是大于a的，所以直接将字符串数组folder升序排序。每次只需判断当前字符串，是否是父文件夹数组v最后一个字符串的子文件夹即可，细节看注释。

C++版本：

class Solution {
public:
	// 判断a是否是b的前缀，且b[a.size()]=='/'
    bool check(string a,string b){
        if(a.size()>b.size()) return false;
        for(int i=0;i<a.size();i++){
            if(a[i]!=b[i]) return false;
        }
        if(b.size()>a.size() &&b[a.size()]=='/') return true;
        return false;
    }
    vector<string> removeSubfolders(vector<string>& folder) {
    	// 升序
        sort(folder.begin(),folder.end());
        // 答案：父文件夹数组
        vector<string> v;
        v.push_back(folder[0]);
        for(int i=1;i<folder.size();i++){
            string last=v.back();
            string t=folder[i];
            // 判断last是否是t的前缀，且t[last.size()]=='/'
            if(check(last,t)==false){
                v.push_back(t);
            }
        }
        return v;
    }
};

JAVA版本：

class Solution {
    boolean check(String a,String b){
        if(a.length()>b.length()) return false;
        for(int i=0;i<a.length();i++){
            if(a.charAt(i)!=b.charAt(i)) return false;
        }
        if(b.length()>a.length() &&b.charAt(a.length())=='/') return true;
        return false;
    }
    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        List<String> v = new ArrayList<>();
        v.add(folder[0]);
        for(int i=1;i<folder.length;i++){
            String last=v.getLast();
            String t=folder[i];
            if(check(last,t)==false){
                v.add(t);
            }
        }
        return v;
    }
}

GO版本：

func removeSubfolders(folder []string) []string {
    slices.Sort(folder)
    v:=[]string{folder[0]}
    for i:=1;i<len(folder);i++ {
        last:=v[len(v)-1]
        t:=folder[i]
        if check(last,t)==false {
            v=append(v,t)
        }
    }
    return v
}
func check(a,b string) bool {
    if len(a)>len(b) {return false}
    for i,_:=range a {
        if a[i]!=b[i] {
            return false
        }
    }
    if len(b)>len(a) && b[len(a)]=='/' {return true}
    return false
}