(LeetCode 每日一题) 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
}