1233. Remove Sub-Folders from the Filesystem
给一个档案的清单 folder
把所有子档案全部删掉后回传新的清单
folder[i]的子档案必须以folder[i]开头并且接上"/"
思路:
(1)
用字典树，把所有档案都丢到字典树里面
接着去对字典树进行DFS，当遇到结尾就不再往该node继续搜寻下去
这样就可以移除所有子档案
不过这个方法比较慢
(2)
把folder进行排序
排序后把第一个档案丢到ans里
接着往下找如果后续的档案folder[i]
1.跟ans[len(ans)-1]有相同的prefix
2.folder[i][len(ans)]=='/'
满足上面两个条件就是子档案
一直找到不满足上面两个条件的档案丢进ans
接着一直重复上面步骤
就可以得到答案了
code是第二种解法
golang code :
func removeSubfolders(folder []string) []string {
slices.SortFunc(folder, func(i, j string) int {
if i > j {
return 1
}
return -1
})
ans := []string{}
for _, val := range folder {
if len(ans) > 0 {
top := ans[len(ans)-1]
if strings.HasPrefix(val, top) && val[len(top)] == '/' {
continue
}
}
ans = append(ans, val)
}
return ans
}