1233. 删除子文件夹

Posted on | In | |

你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。
如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-sub-folders-from-the-filesystem
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

在官解中这道题有两种解法，一种是基于排序的方法，一种是基于字典树的方法。基于排序的方法就是将所有输入的path进行排序然后再进行相应处理，稍微研究了一下没通过，也觉得不是“正经”解法，这道题应该是可以应用数据结构的，然后看到了方法二，基于字典树的方法。

输入的每条路径中，可以将每一层文件夹当做一个节点，添加一个向量ref，如果节点是输入中的一个路径，则ref为该路径在输入中的索引。将所有路径都保存在字典树中后，对第一层的各节点进行一次深度遍历，只要遇到ref不为-1的节点则将路径添加至答案中，因为后续的都是该节点的子文件夹。
这里仍然还有一个疑点，在dfs函数中的return的写法，没太看懂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Trie:
    def __init__(self):
        self.children = dict()
        self.ref = -1
class Solution(object):
    def removeSubfolders(self, folder):
        """
        :type folder: List[str]
        :rtype: List[str]
        """
        for fold in folder:
            print(fold.split("/")[1:])
        root = Trie()
        for i,fold in enumerate(folder):
            fold = fold.split("/")
            cur = root
            for name in fold:
                if name not in cur.children:
                    cur.children[name] = Trie()
                cur = cur.children[name]
            cur.ref = i
        ans = list()
        def dfs(cur):
            if cur.ref != -1:
                ans.append(folder[cur.ref])
                return
            for child in cur.children.values():
                    dfs(child)
        dfs(root)
        return ans