方法一
解题思路
首先通过字典比较的方式对folder进行排序。由此可知，只有每两个相邻的字符串之间存在子目录情况。因此，folder[i]与folder[i-1]之间满足在值前缀相等并且folder[i-1]的folder[i].length()下标的值为' / '的前提下，那么folder[i-1]为folder[i]的子目录。
复杂度分析 时间复杂度：O(nl⋅logn)。n为文件夹数量，l为文件夹长度，O(nl⋅logn)为排序所消耗的时间。 空间复杂度：O(l)。
代码
代码语言：javascript复制class Solution {
public List<String> removeSubfolders(String[] folder) {
Arrays.sort(folder);
ArrayList<String> list = new ArrayList<String>();
list.add(folder[0]);
for(int i = 1; i < folder.length; i ) {
int pre = list.get(list.size()-1).length();
if(!(pre < folder[i].length()&& list.get(list.size()-1).equals(folder[i].substring(0,pre)) && folder[i].charAt(pre) == '/' )) {
list.add(folder[i]);
}
}
return list;
}
}方法二
解题思路
排序 字典树
代码
```java class Solution { class Trie{ Trie[] chid = new Trie[76]; boolean end; boolean add(String s){ Trie root = this; for(char c:s.toCharArray()){ if(c=='/'&&root.end){ return false; } if(root.chid[c-'/']==null){ root.chid[c-'/'] = new Trie(); } root = root.chid[c-'/']; } root.end = true; return true; } } public List removeSubfolders(String[] folder) { Arrays.sort(folder,(x,y)->(x.length()-y.length())); Trie root = new Trie(); List res = new ArrayList<>(); for(String s:folder){ if(root.add(s)) res.add(s); } return res; } } ``
