1948. Delete Duplicate Folders in System
几天前的每日
思路 :
把file system想像成一颗tree
根据题意如果有两个node的subtree相同的话,那就要被移除
所以把每个node的subtree的值变成一个key
然后在去检查每一个node的key是不是有重复出现
如果有的话就要移除
然后要记得用order_map来记录每个node底下的child,
这样才能保证每次child出现的顺序相同
因为golang没有order_map, 所以我是用unorder_map纪录后, 再重新排序
golang code
type treeNode struct {
val string
next map[string]*treeNode
}
func deleteDuplicateFolder(paths [][]string) [][]string {
root := &treeNode{"/", make(map[string]*treeNode)}
node2key := make(map[*treeNode]string)
keyCounter := make(map[string]int)
for _, path := range paths {
tmp := root
for _, child := range path {
if tmp.next[child] == nil {
tmp.next[child] = &treeNode{child, make(map[string]*treeNode)}
}
tmp = tmp.next[child]
}
}
ans := [][]string{}
getKey(&node2key, &keyCounter, root)
for _, child := range root.next {
dfs(&node2key, &keyCounter, child, []string{}, &ans)
}
return ans
}
func dfs(node2key *map[*treeNode]string, keyCounter *map[string]int, root *
treeNode, curSlice []string, ans *[][]string) {
curSlice = append(curSlice, root.val)
key := (*node2key)[root]
if (*keyCounter)[key] > 1 {
return
}
tmp := make([]string, len(curSlice))
copy(tmp, curSlice)
*ans = append(*ans, tmp)
for _, child := range root.next {
dfs(node2key, keyCounter, child, curSlice, ans)
}
}
func getKey(node2key *map[*treeNode]string, keyCounter *map[string]int, root *
treeNode) string {
type name struct {
val string
node *treeNode
}
keyBuilder := strings.Builder{}
name2Node := make([]name, 0, len(root.next))
for _, child := range root.next {
name2Node = append(name2Node, name{child.val, child})
}
slices.SortFunc(name2Node, func(a, b name) int {
if a.val > b.val {
return 1
}
return -1
})
for _, node := range name2Node {
keyBuilder.WriteString(node.val)
keyBuilder.WriteString(getKey(node2key, keyCounter, node.node))
keyBuilder.WriteString("#")
}
key := keyBuilder.String()
(*node2key)[root] = key
if key != "" {
(*keyCounter)[key]++
return key
}
return "*"
}

内推我

内推我