title

problem link

由于一个漏洞，文件系统中存在许多重复文件夹。给你一个二维数组 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 * 104
• 1 <= paths[i].length <= 500
• 1 <= paths[i][j].length <= 10
• 1 <= sum(paths[i][j].length) <= 2 * 105
• path[i][j] 由小写英文字母组成
• 不会存在两个路径都指向同一个文件夹的情况
• 对于不在根层级的任意文件夹，其父文件夹也会包含在输入中

solution

方法一：子树的序列化表示

思路

我们可以想出这道题在抽象层面（也就是省去了所有实现细节）的解决方法，即：

• 第一步，我们通过给定的 \textit{paths}paths，简历出文件系统的树型表示。这棵树是一棵多叉树，根节点为 \texttt{/}/，每个非根节点表示一个文件夹。

• 第二步，我们对整棵树从根节点开始进行一次遍历。根据题目中的描述，如果两个节点 xx 和 yy 包含的子文件夹的「结构」（即这些子文件夹、子文件夹的子文件夹等等，递归直到空文件夹为止）完全相同，我们就需要将 xx 和 yy 都进行删除。那么，为了得到某一个节点的子文件夹的「结构」，我们应当首先遍历完成该节点的所有子节点，再回溯遍历该节点本身。这就对应着多叉树的后序遍历。

  在回溯到某节点时，我们需要将该节点的「结构」存储下来，记录在某一「数据结构」中，以便于与其它节点的「结构」进行比较。

• 第三步，我们再次对整棵树从根节点开始进行一次遍历。当我们遍历到节点 xx 时，如果 xx 的「结构」在「数据结构」中出现了超过 11 次，那就说明存在于 xx 相同的文件夹，我们就需要将 xx 删除并回溯，否则 xx 是唯一的，我们将从根节点开始到 xx 的路径计入答案，并继续向下遍历 xx 的子节点。

  在遍历完成后，我们就删除了所有重复的文件夹，并且得到了最终的答案。

算法

对于上面的三个步骤，我们依次尝试进行解决。

对于第一步而言，我们只需要定义一个表示树结构的类，建立一个根节点，随后遍历 \textit{paths}paths 中的每一条表示文件夹的路径，将路径上的所有节点加入树中即可。如果读者已经掌握了字典树（Trie）这一数据结构，就可以较快地实现这一步。

对于第二步而言，难点不在于对树进行后序遍历，而在于如何表示一个节点的「结构」。我们可以参考「297. 二叉树的序列化与反序列化」，实现一个多叉树的序列化表示。我们用 \text{serial}(x)serial(x) 记录节点 xx 的序列化表示，具体地：

• 如果节点 xx 是子节点，那么 \text{serial}(x)serial(x) 为空字符串，这是因为节点 xx 中不包含任何文件夹，它没有「结构」。例如示例 11 中，三个叶节点 b, a, ab,a,a 对应的序列化表示均为空字符串；

• 如果节点 xx 不是子节点，它的子节点分别为 y_1, y_2, \cdots, y_ky1,y2,⋯,y**k 那么 \text{serial}(x)serial(x) 递归定义为：

  \text{serial}(x) = y_1(\text{serial}(y_1))y_2(\text{serial}(y_2))\cdots y_k(\text{serial}(y_k))serial(x)=y1(serial(y1))y2(serial(y2))⋯yk*(serial(*yk))

  也就是说，我们首先递归地求出 y_1, y_2, \cdots, y_ky1,y2,⋯,y**k 的序列化表示，随后将它们连通本身的文件夹名拼接在一起，并在外层使用括号 ()() 将它们之间进行区分（或者说隔离）。但如果只是随意地进行拼接，会产生顺序的问题，即如果有节点 x_1x1 和 x_2x2，它们有相同的子节点 y_1y1 和 y_2y2，但在 x_1x1 的子节点中 y_1y1 先出现 y_2y2 后出现，而在 x_2x2 的子节点中 y_2y2 先出现而 y_1y1 后出现，这样尽管 x_1x1 和 x_2x2 的「结构」是完全相同的，但会因为子节点的出现顺序不同，导致序列化的字符串不同。

  因此，在将 y_1, y_2, \cdots, y_ky1,y2,⋯,y**k 的序列化表示进行拼接之前，我们可以对它们进行排序（字典序顺序），再将排序后的结果进行拼接，就可以保证具有相同「结构」的节点的序列化表示是完全相同的了。例如示例 44 中，根节点下方的两个子节点 a, ba,b，它们的序列化表示均为 \texttt{x(y())z()}x(y())z()。

这样一来，通过一次树的后序遍历，我们就可以求出每一个节点「结构」的序列化表示。由于序列化表示都是字符串，因此我们可以使用一个哈希映射，记录每一种序列化表示以及其对应的出现次数。

对于第三步而言，我们从根节点开始对树进行深度优先遍历，并使用一个数组 \textit{path}path 记录从根节点到当前遍历到的节点 xx 的路径。如果 xx 的序列化表示在哈希映射中出现了超过 11 次，就进行回溯，否则将 \textit{path}path 加入答案，并向下递归遍历 xx 的所有子节点。

class Trie:
    serial: str = ""
    children: None

    def __init__(self):
        self.children = {}


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 = collections.Counter()

        def construct(root: Trie):
            if not root or not root.children:
                return
            serial = []
            for k, v in root.children.items():
                construct(v)
                tmp = "{}({})".format(k, v.serial)
                serial.append(tmp)
            serial.sort()
            root.serial = "".join(serial)
            freq[root.serial] += 1

        construct(root)
        ans = []
        path = []

        def operate(node: Trie):
            if not node:
                return
            if freq[node.serial] > 1:
                return
            if path:
                ans.append(path[:])
            for k, v in node.children.items():
                path.append(k)
                operate(v)
                path.pop()

        operate(root)
        return ans



if __name__ == '__main__':
    f = Solution().deleteDuplicateFolder
    print(f(paths = [["a"],["c"],["a","b"],["c","b"],["a","b","x"],["a","b","x","y"],["w"],["w","y"]]))