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 "*"
}

內推我

內推我