Remove Sub Folders From The Filesystem - Leetcode Solution

Problem Statement:

Given a list of folders in a filesystem, you need to delete all the sub-folders in those folders and return a list of the remaining folders.

Example:

Input:

["/a","/a/b","/c/d","/c/d/e","/c/f"]

Output:

["/a","/c/d","/c/f"]

Explanation:

In the input, "/a/b" is a subfolder of "/a" and "/c/d/e" is a subfolder of "/c/d". Therefore, we need to remove these subfolders and return the remaining ones.

Solution:

We can solve this problem using a Trie data structure. We can create a Trie by inserting all the folder names into it. We can then traverse the Trie and remove all the nodes that have more than one child (i.e., subfolders).

Let's go through the steps in more detail:

Step 1: Insert all the folder names into the Trie data structure. We can use the "/" character as the delimiter.

Step 2: Traverse the Trie to identify all the nodes that have more than one child (i.e., subfolders).

Step 3: Remove all the nodes identified in step 2 and their descendants from the Trie.

Step 4: Traverse the Trie again and construct the list of remaining folders by concatenating the folder names along the path from the root to the leaf nodes.

Step 5: Return the list of remaining folders.

Here's the Python code that implements this solution:

class TrieNode: def init(self): self.children = {} self.is_end_of_word = False

class Trie: def init(self): self.root = TrieNode()

def insert(self, word):
    node = self.root
    for char in word.split("/")[1:]:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.is_end_of_word = True

def remove_sub_folders(self):
    def dfs(node):
        if len(node.children) == 0:
            return False

        has_subfolder = False
        for char, child in node.children.items():
            if dfs(child):
                has_subfolder = True
                node.children.pop(char)

        return has_subfolder or node.is_end_of_word

    dfs(self.root)

def get_remaining_folders(self):
    def dfs(node, prefix):
        if node.is_end_of_word:
            remaining_folders.append("/" + prefix)
            return

        for char, child in node.children.items():
            dfs(child, prefix + "/" + char)

    remaining_folders = []
    dfs(self.root, "")
    return remaining_folders

def remove_subfolders(folder: List[str]) -> List[str]: trie = Trie() for f in folder: trie.insert(f)

trie.remove_sub_folders()
return trie.get_remaining_folders()

Time Complexity:

The time complexity of this solution is O(N*M), where N is the number of folders and M is the maximum length of a folder name.

Space Complexity:

The space complexity of this solution is O(N*M), where N is the number of folders and M is the maximum length of a folder name. This is because we need to store all the folder names in the Trie.

1