leetcode1948_删除系统中重复文件

题目

链接：LeetCode1948:删除系统中重复文件

由于一个漏洞，文件系统中存在许多重复文件夹。给你一个二维数组 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] 由小写英文字母组成
• 不会存在两个路径都指向同一个文件夹的情况
• 对于不在根层级的任意文件夹，其父文件夹也会包含在输入中

思路

抽象思路

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

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

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

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

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

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

具体实现

针对第一步，我们可以想到经典的字典树，用于表示我们的文件结构，即每一个节点用一个 map 存储它的子树和 key，当然数组也可以，不过我更习惯于用 map ，然后遍历我们的数组构建字典树即可。

针对第二步，并在字典树中存储一个 data 用于表示它的子树的序列化值，这一步我们不断递归去获取他子树的序列化表示，序列化的方式很多种，我们这边采用的是 子树的值 + (子树的子树序列化的值) 的方式，为了使特殊情况比如 ['a'], ['a', 'b'], ['a', 'c'], ['d'], ['d', 'c'], ['d', 'b']中 a 和 d 的子树序列化值相同，我们需要提前进行预处理排序，我们需要建立一个 map 来存储重复出现的序列化值。

最后我们就遍历我们的字典树，如果一个树节点上的子树序列化值在 map 中的值大于 1，就说明重复出现，舍弃，当然如果该值是叶节点就算了。

答案

/**
 * @param {string[][]} paths
 * @return {string[][]}
 */
var deleteDuplicateFolder = function (paths) {
  let root = new Trie();
  let map = new Map();
  let res = [];
  paths.sort((x, y) => {
    if (x.length !== y.length) {
      return x.length - y.length;
    } else {
      for (let i = 0; i < x.length; i++) {
        if (x[i] !== y[i]) {
          return x[i].charCodeAt() - y[i].charCodeAt();
        }
      }
    }
  });
  paths.forEach((path) => root.insert(path));
  root.serilize(map);
  getRes(root);

  function getRes(root, path = []) {
    if (root.data !== "" && map.get(root.data) > 1) {
      return;
    }
    if (path.length) {
      res.push(path.slice());
    }
    for (let item of root.children.keys()) {
      path.push(item);
      getRes(root.children.get(item), path);
      path.pop();
    }
  }

  return res;
};

class Trie {
  constructor() {
    this.data = "";
    this.children = new Map();
  }

  insert = (path) => {
    let node = this;
    for (let char of path) {
      if (!node.children.has(char)) {
        node.children.set(char, new Trie());
      }
      node = node.children.get(char);
    }
  };

  serilize = (map = new Map()) => {
    for (let child of this.children.keys()) {
      this.data += child + "(" + this.children.get(child).serilize(map) + ")";
    }
    map.set(this.data, (map.get(this.data) || 0) + 1);
    return this.data;
  };
}