1
class Solution {
2
  TrieNode root;
3

4
  public List<String> removeSubfolders(String[] folder) {
5
    List<String> res = new ArrayList<>();
6
    Arrays.sort(folder, (a, b) -> (a.length() - b.length()));
7
    root = new TrieNode();
8
    for (String f : folder) {
9
      if (insert(f)) {
10
        res.add(f);
11
      }
12
    }
13
    return res;
14
  }
15

16
  private boolean insert(String folder) {
17
    TrieNode node = root;
18
    char[] chs = folder.toCharArray();
19
    for (int i = 0; i < chs.length; i++) {
20
      char ch = chs[i];
21
      node.children.putIfAbsent(ch, new TrieNode());
22
      node = node.children.get(ch);
23
      if (node.isFolder && (i + 1 < chs.length && chs[i + 1] == '/')) {
24
        return false;
25
      }
26
    }
27
    node.isFolder = true;
28
    return true;
29
  }
30
}
31

32
class TrieNode {
33
  Map<Character, TrieNode> children = new HashMap<>();
34
  boolean isFolder;
35
}