1948. 删除系统中的重复文件夹Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
由于一个漏洞，文件系统中存在许多重复文件夹。给你一个二维数组 paths，其中 paths[i] 是一个表示文件系统中第 i 个文件夹的绝对路径的数组。
例如，["one", "two", "three"] 表示路径 "/one/two/three" 。 如果两个文件夹（不需要在同一层级）包含 非空且相同的 子文件夹 集合 并具有相同的子文件夹结构，则认为这两个文件夹是相同文件夹。相同文件夹的根层级 不 需要相同。如果存在两个（或两个以上）相同 文件夹，则需要将这些文件夹和所有它们的子文件夹 标记 为待删除。
例如，下面文件结构中的文件夹 "/a" 和 "/b" 相同。它们（以及它们的子文件夹）应该被 全部 标记为待删除：
/a
/a/x
/a/x/y
/a/z
/b
/b/x
/b/x/y
/b/z 然而，如果文件结构中还包含路径 "/b/w" ，那么文件夹 "/a" 和 "/b" 就不相同。注意，即便添加了新的文件夹 "/b/w" ，仍然认为 "/a/x" 和 "/b/x" 相同。
一旦所有的相同文件夹和它们的子文件夹都被标记为待删除，文件系统将会 删除 所有上述文件夹。文件系统只会执行一次删除操作。执行完这一次删除操作后，不会删除新出现的相同文件夹。
返回二维数组 ans ，该数组包含删除所有标记文件夹之后剩余文件夹的路径。路径可以按 任意顺序 返回。
示例 1：
输入：paths = [["a"],["c"],["d"],["a","b"],["c","b"],["d","a"]]
输出：[["d"],["d","a"]]
解释：文件结构如上所示。
文件夹 "/a" 和 "/c"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含名为 "b" 的空文件夹。
示例 2：
输入：paths = [["a"],["c"],["a","b"],["c","b"],["a","b","x"],["a","b","x","y"],["w"],["w","y"]]
输出：[["c"],["c","b"],["a"],["a","b"]]
解释：文件结构如上所示。
文件夹 "/a/b/x" 和 "/w"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含名为 "y" 的空文件夹。
注意，文件夹 "/a" 和 "/c" 在删除后变为相同文件夹，但这两个文件夹不会被删除，因为删除只会进行一次，且它们没有在删除前被标记。
示例 3：
输入：paths = [["a","b"],["c","d"],["c"],["a"]]
输出：[["c"],["c","d"],["a"],["a","b"]]
解释：文件系统中所有文件夹互不相同。
注意，返回的数组可以按不同顺序返回文件夹路径，因为题目对顺序没有要求。
示例 4：
输入：paths = [["a"],["a","x"],["a","x","y"],["a","z"],["b"],["b","x"],["b","x","y"],["b","z"]]
输出：[]
解释：文件结构如上所示。
文件夹 "/a/x" 和 "/b/x"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含名为 "y" 的空文件夹。
文件夹 "/a" 和 "/b"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含一个名为 "z" 的空文件夹以及上面提到的文件夹 "x" 。
示例 5：
输入：paths = [["a"],["a","x"],["a","x","y"],["a","z"],["b"],["b","x"],["b","x","y"],["b","z"],["b","w"]]
输出：[["b"],["b","w"],["b","z"],["a"],["a","z"]]
解释：本例与上例的结构基本相同，除了新增 "/b/w" 文件夹。
文件夹 "/a/x" 和 "/b/x" 仍然会被标记，但 "/a" 和 "/b" 不再被标记，因为 "/b" 中有名为 "w" 的空文件夹而 "/a" 没有。
注意，"/a/z" 和 "/b/z" 不会被标记，因为相同子文件夹的集合必须是非空集合，但这两个文件夹都是空的。
提示：
- 1 <= paths.length <= 2 * 104
- 1 <= paths[i].length <= 500
- 1 <= paths[i][j].length <= 10
- 1 <= sum(paths[i][j].length) <= 2 * 105
- path[i][j] 由小写英文字母组成
- 不会存在两个路径都指向同一个文件夹的情况
- 对于不在根层级的任意文件夹，其父文件夹也会包含在输入中
# 思路
dfs
# 解法
class Solution {
List<List<String>> ret = new ArrayList<>();
public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {
//node非叶子节点，且结构一致 -> 判断节点的hash函数
Trie root = new Trie();
for(int i=0;i<paths.size();i++){
Trie cur = root;
for(String s : paths.get(i)){
cur.child.putIfAbsent(s, new Trie());
cur = cur.child.get(s);
cur.name = s;
}
}
List<String> p = new ArrayList<>();
Map<String, Integer> cnt = new HashMap<>();
dfs(root, cnt);
search(root, cnt, p);
return ret;
}
public void search(Trie cur, Map<String, Integer> cnt, List<String> p){
if(cur.isDelete==1) return;
int x = 0;
if(cur.name!="/"){
p.add(cur.name);
ret.add(new ArrayList<>(p));
x = 1;
}
if(cur.child.size()==0){
p.remove(p.size()-1);
return;
}
for(Trie chi : cur.child.values()){
if(cnt.getOrDefault(chi.s, 0)>1){
chi.isDelete = 1;
}
search(chi, cnt, p);
}
if(x==1) p.remove(p.size()-1);
}
public String dfs(Trie cur, Map<String, Integer> cnt){
if(cur.child.size()==0){
return '('+cur.name+')';
}
List<String> l = new ArrayList<>();
for(Trie chi : cur.child.values()){
l.add('('+dfs(chi, cnt)+')');
}
Collections.sort(l);
StringBuilder sb = new StringBuilder();
sb.append(cur.name);
for(String s : l) sb.append(s);
String temp = sb.toString().substring(cur.name.length());
cnt.put(temp, cnt.getOrDefault(temp, 0)+1);
cur.s = temp;
return sb.toString();
}
}
class Trie{
int isDelete; //是否需要删除
String s; //节点的子结构对应的字符串
String name; //节点自己的名字
Map<String, Trie> child;
public Trie(){
child = new HashMap<>();
isDelete = 0;
name = "/";
s = "/";
}
}
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
# 总结
- 分析出几种情况，然后分别对各个情况实现
