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
}