Skip to content

1948. Delete Duplicate Folders in System 👍

  • Time: $O(10 \cdot \Sigma |\texttt{paths[i][j]}|)$
  • Space: $O(10 \cdot \Sigma |\texttt{paths[i][j]}|)$
 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
struct TrieNode {
  unordered_map<string, shared_ptr<TrieNode>> children;
  bool deleted = false;
};

class Solution {
 public:
  vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {
    vector<vector<string>> ans;
    vector<string> path;
    unordered_map<string, vector<shared_ptr<TrieNode>>> subtreeToNodes;

    ranges::sort(paths);

    for (const vector<string>& path : paths) {
      shared_ptr<TrieNode> node = root;
      for (const string& s : path) {
        if (!node->children.contains(s))
          node->children[s] = make_shared<TrieNode>();
        node = node->children[s];
      }
    }

    buildSubtreeToRoots(root, subtreeToNodes);

    for (const auto& [_, nodes] : subtreeToNodes)
      if (nodes.size() > 1)
        for (shared_ptr<TrieNode> node : nodes)
          node->deleted = true;

    constructPath(root, path, ans);
    return ans;
  }

 private:
  shared_ptr<TrieNode> root = make_shared<TrieNode>();

  string buildSubtreeToRoots(
      shared_ptr<TrieNode> node,
      unordered_map<string, vector<shared_ptr<TrieNode>>>& subtreeToNodes) {
    string subtree = "(";
    for (const auto& [s, child] : node->children)
      subtree += s + buildSubtreeToRoots(child, subtreeToNodes);
    subtree += ")";
    if (subtree != "()")
      subtreeToNodes[subtree].push_back(node);
    return subtree;
  }

  void constructPath(shared_ptr<TrieNode> node, vector<string>& path,
                     vector<vector<string>>& ans) {
    for (const auto& [s, child] : node->children)
      if (!child->deleted) {
        path.push_back(s);
        constructPath(child, path, ans);
        path.pop_back();
      }
    if (!path.empty())
      ans.push_back(path);
  }
};

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class TrieNode {
  public Map<String, TrieNode> children = new HashMap<>();
  public boolean deleted = false;
}

class Solution {
  public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {
    List<List<String>> ans = new ArrayList<>();
    Map<String, List<TrieNode>> subtreeToNodes = new HashMap<>();

    Collections.sort(paths, (a, b) -> {
      for (int i = 0; i < Math.min(a.size(), b.size()); ++i) {
        final int c = a.get(i).compareTo(b.get(i));
        if (c != 0)
          return c;
      }
      return Integer.compare(a.size(), b.size());
    });

    for (List<String> path : paths) {
      TrieNode node = root;
      for (final String s : path) {
        node.children.putIfAbsent(s, new TrieNode());
        node = node.children.get(s);
      }
    }

    buildSubtreeToRoots(root, subtreeToNodes);

    for (List<TrieNode> nodes : subtreeToNodes.values())
      if (nodes.size() > 1)
        for (TrieNode node : nodes)
          node.deleted = true;

    constructPath(root, new ArrayList<>(), ans);
    return ans;
  }

  private TrieNode root = new TrieNode();

  private StringBuilder buildSubtreeToRoots(TrieNode node,
                                            Map<String, List<TrieNode>> subtreeToNodes) {
    StringBuilder sb = new StringBuilder("(");
    for (final String s : node.children.keySet()) {
      TrieNode child = node.children.get(s);
      sb.append(s).append(buildSubtreeToRoots(child, subtreeToNodes));
    }
    sb.append(")");
    final String subtree = sb.toString();
    if (!subtree.equals("()")) {
      subtreeToNodes.putIfAbsent(subtree, new ArrayList<>());
      subtreeToNodes.get(subtree).add(node);
    }
    return sb;
  }

  private void constructPath(TrieNode node, List<String> path, List<List<String>> ans) {
    for (final String s : node.children.keySet()) {
      TrieNode child = node.children.get(s);
      if (!child.deleted) {
        path.add(s);
        constructPath(child, path, ans);
        path.remove(path.size() - 1);
      }
    }
    if (!path.isEmpty())
      ans.add(new ArrayList<>(path));
  }
}

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class TrieNode:
  def __init__(self):
    self.children: dict[str, TrieNode] = collections.defaultdict(TrieNode)
    self.deleted = False


class Solution:
  def deleteDuplicateFolder(self, paths: list[list[str]]) -> list[list[str]]:
    ans = []
    root = TrieNode()
    subtreeToNodes: dict[str, list[TrieNode]] = collections.defaultdict(list)

    # Construct the Trie
    for path in sorted(paths):
      node = root
      for s in path:
        node = node.children[s]

    # For each subtree, fill in the {subtree encoding: [root]} hash table
    def buildSubtreeToRoots(node: TrieNode) -> str:
      subtree = '(' + ''.join(s + buildSubtreeToRoots(node.children[s])
                              for s in node.children) + ')'
      if subtree != '()':
        subtreeToNodes[subtree].append(node)
      return subtree

    buildSubtreeToRoots(root)

    # Mark nodes that should be deleted
    for nodes in subtreeToNodes.values():
      if len(nodes) > 1:
        for node in nodes:
          node.deleted = True

    # Construct the answer array for nodes that haven't been deleted
    def constructPath(node: TrieNode, path: list[str]) -> None:
      for s, child in node.children.items():
        if not child.deleted:
          constructPath(child, path + [s])
      if path:
        ans.append(path)

    constructPath(root, [])
    return ans