How hard is LeetCode 1948. Delete Duplicate Folders in System?

LeetCode 1948. Delete Duplicate Folders in System is rated Hard on LeetCode.

What is the time complexity of LeetCode 1948. Delete Duplicate Folders in System?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1948. Delete Duplicate Folders in System?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1948. Delete Duplicate Folders in System cover?

LeetCode 1948. Delete Duplicate Folders in System is tagged Trie, Array, Hash Table, String and Hash Function on LeetCode.

Delete Duplicate Folders in System — LeetCode 1948 Python Solution

HardTrieArrayHash TableStringHash Function

Problem: #1948
Pattern: Trie
Reading time: 8 min
Source: leetcode.com

The problem

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.

Example

Input: paths = [["a"],["c"],["d"],["a","b"],["c","b"],["d","a"]]
Output: [["d"],["d","a"]]
Explanation: The file structure is as shown.

Python solution

Python

class Trie:
    def __init__(self):
        self.children: Dict[str, "Trie"] = defaultdict(Trie)
        self.deleted: bool = False


class Solution:
    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:
        root = Trie()
        for path in paths:
            cur = root
            for name in path:
                if cur.children[name] is None:
                    cur.children[name] = Trie()
                cur = cur.children[name]

        g: Dict[str, Trie] = {}

        def dfs(node: Trie) -> str:
            if not node.children:
                return ""
            subs: List[str] = []
            for name, child in node.children.items():
                subs.append(f"{name}({dfs(child)})")
            s = "".join(sorted(subs))
            if s in g:
                node.deleted = g[s].deleted = True
            else:
                g[s] = node
            return s

        def dfs2(node: Trie) -> None:
            if node.deleted:
                return
            if path:
                ans.append(path[:])
            for name, child in node.children.items():
                path.append(name)
                dfs2(child)
                path.pop()

        dfs(root)
        ans: List[List[str]] = []
        path: List[str] = []
        dfs2(root)
        return ans

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 1948. Delete Duplicate Folders in System is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1948. Delete Duplicate Folders in System?: LeetCode 1948. Delete Duplicate Folders in System is rated Hard on LeetCode.
What is the time complexity of LeetCode 1948. Delete Duplicate Folders in System?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1948. Delete Duplicate Folders in System?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1948. Delete Duplicate Folders in System cover?: LeetCode 1948. Delete Duplicate Folders in System is tagged Trie, Array, Hash Table, String and Hash Function on LeetCode.