1948. Delete Duplicate Folders in System LeetCode Solution

In this guide, you will get 1948. Delete Duplicate Folders in System LeetCode Solution with the best time and space complexity. The solution to Delete Duplicate Folders in System problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Delete Duplicate Folders in System solution in C++
  4. Delete Duplicate Folders in System solution in Java
  5. Delete Duplicate Folders in System solution in Python
  6. Additional Resources
1948. Delete Duplicate Folders in System LeetCode Solution image

Problem Statement of Delete Duplicate Folders in System

Due to a bug, there are many duplicate folders in a file system. You are given a 2D array paths, where paths[i] is an array representing an absolute path to the ith folder in the file system.

For example, [“one”, “two”, “three”] represents the path “/one/two/three”.

Two folders (not necessarily on the same level) are identical if they contain the same non-empty set of identical subfolders and underlying subfolder structure. The folders do not need to be at the root level to be identical. If two or more folders are identical, then mark the folders as well as all their subfolders.

For example, folders “/a” and “/b” in the file structure below are identical. They (as well as their subfolders) should all be marked:

/a
/a/x
/a/x/y
/a/z
/b
/b/x
/b/x/y
/b/z

However, if the file structure also included the path “/b/w”, then the folders “/a” and “/b” would not be identical. Note that “/a/x” and “/b/x” would still be considered identical even with the added folder.

See also  766. Toeplitz Matrix LeetCode Solution

Once all the identical folders and their subfolders have been marked, the file system will delete all of them. The file system only runs the deletion once, so any folders that become identical after the initial deletion are not deleted.
Return the 2D array ans containing the paths of the remaining folders after deleting all the marked folders. The paths may be returned in any order.

Example 1:

Input: paths = [[“a”],[“c”],[“d”],[“a”,”b”],[“c”,”b”],[“d”,”a”]]
Output: [[“d”],[“d”,”a”]]
Explanation: The file structure is as shown.
Folders “/a” and “/c” (and their subfolders) are marked for deletion because they both contain an empty
folder named “b”.

Example 2:

Input: paths = [[“a”],[“c”],[“a”,”b”],[“c”,”b”],[“a”,”b”,”x”],[“a”,”b”,”x”,”y”],[“w”],[“w”,”y”]]
Output: [[“c”],[“c”,”b”],[“a”],[“a”,”b”]]
Explanation: The file structure is as shown.
Folders “/a/b/x” and “/w” (and their subfolders) are marked for deletion because they both contain an empty folder named “y”.
Note that folders “/a” and “/c” are identical after the deletion, but they are not deleted because they were not marked beforehand.

Example 3:

Input: paths = [[“a”,”b”],[“c”,”d”],[“c”],[“a”]]
Output: [[“c”],[“c”,”d”],[“a”],[“a”,”b”]]
Explanation: All folders are unique in the file system.
Note that the returned array can be in a different order as the order does not matter.

Constraints:

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] consists of lowercase English letters.
No two paths lead to the same folder.
For any folder not at the root level, its parent folder will also be in the input.

Complexity Analysis

  • Time Complexity: O(10 \cdot \Sigma |\texttt{paths[i][j]}|)
  • Space Complexity: O(10 \cdot \Sigma |\texttt{paths[i][j]}|)

1948. Delete Duplicate Folders in System LeetCode Solution in C++

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);
  }
};
/* code provided by PROGIEZ */

1948. Delete Duplicate Folders in System LeetCode Solution in Java

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));
  }
}
// code provided by PROGIEZ

1948. Delete Duplicate Folders in System LeetCode Solution in Python

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
# code by PROGIEZ

Additional Resources

See also  1992. Find All Groups of Farmland LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.