# 1233. Remove Sub-Folders from the Filesystem
###### tags: `Leetcode` `Medium` `FaceBook` `Trie`
Link: https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/
## 思路
### 思路一 $O(MNlogN)$ $O(1)$
排序
然后如果答案是空的或者下一个string不是以答案的最后一个字串开始的，就加进答案
时间复杂度分析:
n = folder.length, m = average size of the strings in folder
Because the sort is based on merge sort for Object and time complexity of merge sort is O(n * logn). That means n * logn times comparing happened.
For this question, it just makes the comparing time be O(m). Thus it won't increase the number of "layers" of merge sort to log(n * m).
### 思路二 $O(MN)$ $O(MN)$
Trie
每个node都表示一个folder(路径经过split完之后的结果)，用hashmap存它的下一个string和对应的trienode
如果当前TrieNode是一个路径的结尾，index就会标成这条路径在string array里面的index
建完trie之后，用bfs遍历，然后一个node的index>=0，就把folder[index]加进答案里面，并且下面的所有child都不需要遍历了
## Code
### 思路一

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        List<String> ans = new ArrayList<>();
        for(String str:folder){
            if(ans.isEmpty() || !(str.startsWith(ans.get(ans.size()-1)+'/'))){
                ans.add(str);
            }
        }
        return ans;
    }
}

### 思路二

class Solution {
    class TrieNode{
        Map<String, TrieNode> map = new HashMap<>();
        int index = -1;
    }
    
    TrieNode root = new TrieNode();
    List<String> ans = new ArrayList<>();
    
    public List<String> removeSubfolders(String[] folders) {
        for(int j = 0;j < folders.length;j++){
            String[] splited = folders[j].split("/");
            TrieNode curr = root;
            for(int i = 0;i < splited.length;i++){
                if(!curr.map.containsKey(splited[i])){
                    curr.map.put(splited[i], new TrieNode());
                }
                curr = curr.map.get(splited[i]);
            }
            curr.index = j;
        }
        Queue<TrieNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TrieNode curr = q.poll();
            if(curr.index>=0) ans.add(folders[curr.index]);
            else{
                for(TrieNode child:curr.map.values()){
                    q.add(child);
                }
            }
        }
        return ans;
    }
}