题目:
思想:
脑子里的构思是字典树,但是是C语言
的字典树,无论是Python
还是 golang
我都不会写。 所以无奈只能看看答案。
ylb大佬先是对list进行了排序,然后遍历列表。
1.如果i的前[len(ans[-1])]
恰好和ans[-1]
的元素一致,就说明i是
ans[-1]的子文件夹,则跳过。
2.如果是["/a/b/c","/a/b/ca","/a/b/d"]
这种情况,光靠1.的判断是不够的,这个时候"/a/b/ca"
的前缀和"/a/b/c"
是一样的,但是ca和c实际上是两个不同的文件夹,所以还要加上一个判断前缀末尾
是否是/
,"/a/b/ca"
和"/a/b/c/a"
中后者才会被判定是前面一个元素的子集。
字典树没太看懂:
我们可以使用字典树存储数组 folder 中的所有文件夹。
字典树的每个节点包含 children 字段,用于存储当前节点的子节点,以及 fid 字段,
用于存储当前节点对应的文件夹在数组 folder 中的下标。
对于数组 folder 中的每个文件夹 f,我们先将 f 按照 / 分割成若干个子串,
然后从根节点开始,依次将子串加入字典树中。接下来,我们从根节点开始搜索字典树,
如果当前节点的 fid 字段不为 -1,则说明当前节点对应的文件夹是答案数组中的一个文件夹,
我们将其加入答案数组并且返回。否则,我们递归地搜索当前节点的所有子节点,最终返回答案数组。
代码:
1 | class Solution: |
1 | func removeSubfolders(folder []string) (ans []string) { |