删除系统中的重复文件夹

难度: Hard

由于一个漏洞，文件系统中存在许多重复文件夹。给你一个二维数组 paths，其中 paths[i] 是一个表示文件系统中第 i 个文件夹的绝对路径的数组。

例如，["one", "two", "three"] 表示路径 "/one/two/three" 。

如果两个文件夹（不需要在同一层级）包含 非空且相同的 子文件夹集合并具有相同的子文件夹结构，则认为这两个文件夹是相同文件夹。相同文件夹的根层级不需要相同。如果存在两个（或两个以上）相同文件夹，则需要将这些文件夹和所有它们的子文件夹标记为待删除。

例如，下面文件结构中的文件夹 "/a" 和 "/b" 相同。它们（以及它们的子文件夹）应该被全部标记为待删除：
- /a
- /a/x
- /a/x/y
- /a/z
- /b
- /b/x
- /b/x/y
- /b/z
然而，如果文件结构中还包含路径 "/b/w" ，那么文件夹 "/a" 和 "/b" 就不相同。注意，即便添加了新的文件夹 "/b/w" ，仍然认为 "/a/x" 和 "/b/x" 相同。

一旦所有的相同文件夹和它们的子文件夹都被标记为待删除，文件系统将会删除所有上述文件夹。文件系统只会执行一次删除操作。执行完这一次删除操作后，不会删除新出现的相同文件夹。

返回二维数组 ans ，该数组包含删除所有标记文件夹之后剩余文件夹的路径。路径可以按 任意顺序 返回。

示例 1：

输入：paths = [["a"],["c"],["d"],["a","b"],["c","b"],["d","a"]]
输出：[["d"],["d","a"]]
解释：文件结构如上所示。
文件夹 "/a" 和 "/c"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含名为 "b" 的空文件夹。

示例 2：

输入：paths = [["a"],["c"],["a","b"],["c","b"],["a","b","x"],["a","b","x","y"],["w"],["w","y"]]
输出：[["c"],["c","b"],["a"],["a","b"]]
解释：文件结构如上所示。
文件夹 "/a/b/x" 和 "/w"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含名为 "y" 的空文件夹。
注意，文件夹 "/a" 和 "/c" 在删除后变为相同文件夹，但这两个文件夹不会被删除，因为删除只会进行一次，且它们没有在删除前被标记。

示例 3：

输入：paths = [["a","b"],["c","d"],["c"],["a"]]
输出：[["c"],["c","d"],["a"],["a","b"]]
解释：文件系统中所有文件夹互不相同。
注意，返回的数组可以按不同顺序返回文件夹路径，因为题目对顺序没有要求。

示例 4：

输入：paths = [["a"],["a","x"],["a","x","y"],["a","z"],["b"],["b","x"],["b","x","y"],["b","z"]]
输出：[]
解释：文件结构如上所示。
文件夹 "/a/x" 和 "/b/x"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含名为 "y" 的空文件夹。
文件夹 "/a" 和 "/b"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含一个名为 "z" 的空文件夹以及上面提到的文件夹 "x" 。

示例 5：

输入：paths = [["a"],["a","x"],["a","x","y"],["a","z"],["b"],["b","x"],["b","x","y"],["b","z"],["b","w"]]
输出：[["b"],["b","w"],["b","z"],["a"],["a","z"]]
解释：本例与上例的结构基本相同，除了新增 "/b/w" 文件夹。
文件夹 "/a/x" 和 "/b/x" 仍然会被标记，但 "/a" 和 "/b" 不再被标记，因为 "/b" 中有名为 "w" 的空文件夹而 "/a" 没有。
注意，"/a/z" 和 "/b/z" 不会被标记，因为相同子文件夹的集合必须是非空集合，但这两个文件夹都是空的。

提示：

1 <= paths.length <= 2 * 10⁴
1 <= paths[i].length <= 500
1 <= paths[i][j].length <= 10
1 <= sum(paths[i][j].length) <= 2 * 10⁵
path[i][j] 由小写英文字母组成
不会存在两个路径都指向同一个文件夹的情况
对于不在根层级的任意文件夹，其父文件夹也会包含在输入中

Submission

运行时间: 261 ms

内存: 45.4 MB

class Trie:
    #当前节点结构的序列化表示
    serial: str = ""
    #当前节点的子节点。
    children: dict

    def __init__(self):
        self.children = dict()

class Solution:
    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:
         # 根节点
        root = Trie()

        for path in paths:
            cur = root
            for node in path:
                if node not in cur.children:
                    cur.children[node] = Trie()
                cur = cur.children[node]

        # 哈希表记录每一种序列化表示的出现次数
        freq = Counter()
        # 基于深度优先搜索的后序遍历，计算每一个节点结构的序列化表示
        def construct(node: Trie) -> None:
            # 如果是叶节点，那么序列化表示为空字符串，无需进行任何操作
            if not node.children:
                return

            v = list()
            # 如果不是叶节点，需要先计算子节点结构的序列化表示
            for folder, child in node.children.items():
                construct(child)
                v.append(folder + "(" + child.serial + ")")
            
            # 防止顺序的问题，需要进行排序
            v.sort()
            node.serial = "".join(v)
            # 计入哈希表
            freq[node.serial] += 1

        construct(root)

        ans = list()
        # 记录根节点到当前节点的路径
        path = list()

        def operate(node: Trie) -> None:
            # 如果序列化表示在哈希表中出现了超过 1 次，就需要删除
            if freq[node.serial] > 1:
                return
            # 否则将路径加入答案
            if path:
                ans.append(path[:])

            for folder, child in node.children.items():
                path.append(folder)
                operate(child)
                path.pop()

        operate(root)
        return ans

Explain

此题解使用字典树(Trie)和序列化的方法来识别和删除重复的文件夹。首先，利用Trie树将每个路径按照文件夹的层级结构构建成树形结构。然后，使用深度优先搜索(DFS)对每个节点进行后序遍历，将每个节点的子树结构序列化成字符串形式。通过这种序列化，可以轻易地比较不同节点的子树结构是否相同。使用一个哈希表来记录每种序列化表示的出现频率。最后，再次使用DFS遍历Trie树，此次遍历时，根据序列化字符串的出现次数判断该节点是否应被删除。如果某个节点的序列化表示出现超过一次，则其对应的文件夹及子文件夹都标记为删除。最终，将所有未被标记删除的文件夹路径收集并返回。

时间复杂度: O(N*L + N*S*log(S))

空间复杂度: O(N*L)

class Trie:
    # 当前节点结构的序列化表示
    serial: str = ""
    # 当前节点的子节点。
    children: dict

    def __init__(self):
        self.children = dict()

class Solution:
    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:
        root = Trie()  # 根节点

        for path in paths:
            cur = root
            for node in path:
                if node not in cur.children:
                    cur.children[node] = Trie()
                cur = cur.children[node]

        freq = Counter()  # 哈希表记录每一种序列化表示的出现次数

        def construct(node: Trie) -> None:
            if not node.children:
                return

            v = list()
            for folder, child in node.children.items():
                construct(child)
                v.append(folder + "(" + child.serial + ")")
            v.sort()
            node.serial = "".join(v)
            freq[node.serial] += 1

        construct(root)

        ans = list()
        path = list()

        def operate(node: Trie) -> None:
            if freq[node.serial] > 1:
                return
            if path:
                ans.append(path[:])

            for folder, child in node.children.items():
                path.append(folder)
                operate(child)
                path.pop()

        operate(root)
        return ans

Explore

在构建Trie树的过程中，每个节点使用一个字典（children）来存储其子节点。当添加一个新的文件夹名到某个节点时，首先检查这个文件夹名是否已经作为当前节点的一个子节点存在。这是通过检查文件夹名是否为字典的一个键来实现的。如果文件夹名不存在，则创建一个新的Trie节点，并将其添加到字典中，使用文件夹名作为键。这种方式确保了每个文件夹名在各自的父节点下只被添加一次，从而避免了重复添加相同的文件夹名，确保了树结构的正确性。

在序列化节点时对子节点名称进行排序是为了保证无论子节点的添加顺序如何，生成的序列化字符串都是一致的。这一步骤是必要的，因为不同的添加顺序可能会导致生成不同的序列化字符串，即使子树的结构是相同的。通过对子节点名称进行排序，可以确保相同结构的子树在序列化时生成相同的字符串，从而允许我们正确地通过比较序列化字符串来识别重复的子树结构。

在`construct`函数中，序列化字符串的构建是通过后序遍历实现的。具体来说，首先对每个节点的所有子节点递归调用`construct`函数，然后从每个子节点获取其序列化字符串。获取到子节点的序列化字符串后，将每个子节点的名称与其序列化字符串结合（格式为`folderName(child.serial)`），并将这些组合字符串存入列表。随后，对这个列表进行排序（以确保顺序一致性），然后将排序后的列表合并成一个单一的字符串。这个合并后的字符串即为当前节点的序列化表示。此字符串反映了当前节点下所有子树的结构。

如果两个完全不同的路径导致相同的序列化输出，这意味着尽管这些路径在树中的位置不同，但它们具有相同的子树结构。在这种情况下，这些结构化相同的子树将被视为重复的，根据题目的要求，将会被删除。哈希表记录的是每个序列化字符串的出现频率，如果某个序列化字符串的出现频率大于1，那么所有对应这个序列化字符串的节点和它们的子节点都将被标记为删除。这确保了所有结构重复的子树都被识别和删除，符合题目的要求。