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
|
import "sort"
type Trie struct {
ch map[string]*Trie
del bool
}
func serialize(node *Trie, mp map[string]int) string {
if len(node.ch) == 0 {
return ""
}
v := make([][2]string, 0, len(node.ch))
for k, child := range node.ch {
v = append(v, [2]string{k, serialize(child, mp)})
}
sort.Slice(v, func(i, j int) bool { return v[i][0] < v[j][0] })
s := ""
for _, kv := range v {
s += "(" + kv[0] + kv[1] + ")"
}
mp[s]++
return s
}
func mark(node *Trie, mp map[string]int) {
if len(node.ch) == 0 {
return
}
v := make([][2]string, 0, len(node.ch))
for k, child := range node.ch {
v = append(v, [2]string{k, serialize(child, mp)})
}
sort.Slice(v, func(i, j int) bool { return v[i][0] < v[j][0] })
s := ""
for _, kv := range v {
s += "(" + kv[0] + kv[1] + ")"
}
if mp[s] > 1 {
node.del = true
}
for _, child := range node.ch {
mark(child, mp)
}
}
func collect(node *Trie, path []string, ans *[][]string) {
for k, child := range node.ch {
if child.del {
continue
}
path = append(path, k)
*ans = append(*ans, append([]string{}, path...))
collect(child, path, ans)
path = path[:len(path)-1]
}
}
func deleteDuplicateFolder(paths [][]string) [][]string {
root := &Trie{ch: map[string]*Trie{}}
for _, p := range paths {
cur := root
for _, s := range p {
if cur.ch[s] == nil {
cur.ch[s] = &Trie{ch: map[string]*Trie{}}
}
cur = cur.ch[s]
}
}
mp := map[string]int{}
serialize(root, mp)
mark(root, mp)
ans := [][]string{}
collect(root, []string{}, &ans)
return ans
}
|