1233. 删除子文件夹

方法一

image-20230208100258492

解题思路

首先通过字典比较的方式对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)。

代码

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;
    }
}

方法二

image-20230208100622491

解题思路

排序+字典树

代码

```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; } } ``