05 August 2008
给定文件夹列表，在删除这些文件夹中的所有子文件夹后返回文件夹。您可以按任何顺序返回答案。
如果文件夹[i] 位于另一个文件夹[j] 中，则称为它的子文件夹。
路径的格式是一个或多个以下形式的连接字符串：’/’ 后跟一个或多个小写英文字母。
例如，“/leetcode”和“/leetcode/problems”是有效路径，而空字符串和“/”不是。
Trie
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public List<String> removeSubfolders(String[] folder) {
List<String> ret = new ArrayList<String>();
if (folder == null)
return ret;
Trie node = new Trie();
for (String f : folder) {
node.add(f.split("/"), 0);
}
for (String f : folder) {
if (node.check(f.split("/"), 0))
ret.add(f);
}
return ret;
}
class Trie {
boolean end = false;
HashMap<String, Trie> next = new HashMap<String, Trie>();
void add(String[] path, int pos) {
if (pos >= path.length) {
this.end = true;
return;
} else {
if (next.containsKey(path[pos]))
next.get(path[pos]).add(path, pos + 1);
else {
Trie node = new Trie();
node.add(path, pos + 1);
next.put(path[pos], node);
}
}
}
boolean check(String[] path, int pos) {
if (next.containsKey(path[pos]))
if (next.get(path[pos]).end)
return pos == path.length - 1;
else
return next.get(path[pos]).check(path, pos + 1);
else return false;
}
}
}
排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public List<String> removeSubfolders(String[] fs) {
Arrays.sort(fs, (a, b) -> a.split("/").length - b.split("/").length);
Set<String> vs = new HashSet<>();
for (String f : fs) {
String[] ds = f.split("/");
StringBuilder sb = new StringBuilder();
boolean found = false;
for (int i = 1; i < ds.length; i++) {
String d = ds[i];
sb.append("/").append(d);
if (vs.contains(sb.toString())) {
found = true;
break;
}
}
if (!found) vs.add(sb.toString());
}
List<String> res = new ArrayList<>();
res.addAll(vs);
return res;
}
}