Delete Duplicate Folders in System LeetCode solution in C++

1
struct Trie {
2
  void insert(const vector<string> &path) {
3
    auto node = this;
4
    for (auto &p : path) {
5
      if (!node->children.count(p)) {
6
        node->children[p] = make_unique<Trie>();
7
      }
8
      node = node->children[p].get();
9
    }
10
  }
11
  map<string, unique_ptr<Trie>> children;
12
};
13

14
class Solution {
15
  Trie root;
16

17
  map<string, Trie *> seen;
18
  unordered_set<Trie *> toDelete;
19

20
  string deduplicate(Trie *node) {
21
    string path;
22
    for (auto &[s, n] : node->children) {
23
      path += s + deduplicate(n.get());
24
    }
25
    if (path.empty()) return "";
26

27
    if (seen.count(path)) {
28
      toDelete.insert(seen[path]);
29
      toDelete.insert(node);
30
    } else
31
      seen[path] = node;
32

33
    return "(" + path + ")";
34
  }
35

36
  void getPaths(Trie *node, vector<vector<string>> &paths, vector<string> &path) {
37
    for (auto &[s, n] : node->children) {
38
      if (toDelete.count(n.get())) continue;
39
      path.push_back(s);
40
      getPaths(n.get(), paths, path);
41
      path.pop_back();
42
    }
43

44
    if (!path.empty()) paths.push_back(path);
45
  }
46

47
 public:
48
  vector<vector<string>> deleteDuplicateFolder(vector<vector<string>> &paths) {
49
    for (auto &path : paths) root.insert(path);
50
    paths.clear();
51
    deduplicate(&root);
52
    getPaths(&root, paths, vector<string>() = {});
53
    return paths;
54
  }
55
};