Leetcode Daily Question 25/10/2024 - 1233. Remove Sub-Folders from the Filesystem

Problem Description:

Given a list of folders folder, return the folders after removing all sub-folders in those folders. You may return the answer in any order. | --------------------------------------------------- | If a folder[i] is located within another folder[j], it is called a sub-folder of it. A sub-folder of folder[j] must start with folder[j], followed by a "/". For example, "/a/b" is a sub-folder of "/a", but "/b" is not a sub-folder of "/a/b/c". | --------------------------------------------------- | The format of a path is one or more concatenated strings of the form: '/' followed by one or more lowercase English letters. | --------------------------------------------------- | For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string and "/" are not.

# Version 1: Trie
from typing import List
class TrieNode:
  def __init__(self):
    self.children = {}
    self.isEnd = False

class Solution:
  def removeSubfolders(self, folder: List[str]) -> List[str]:
    root = TrieNode()
    
    for f in folder:
      current = root
      for path in f.split("/"):
        if path:
          if path not in current.children:
            current.children[path] = TrieNode()
          current = current.children[path]
      current.isEnd = True
      
      
    result = []
    
    def dfs(node, path):
      if node.isEnd:
        result.append(path)
        return
      for part, child in node.children.items():
        dfs(child, path + "/" + part)
    

    dfs(root, "")
    return result
      


# Version 2: Startswith
from typing import List
class Solution:
  def removeSubfolders(self, folder: List[str]) -> List[str]:
    result = []
    folder.sort()
    prev = ""
    for f in folder:
      if not f.startswith(prev + "/") or not prev:
        result.append(f)
        prev = f
    return result

Explanation:

We can solve this by checking if a pattern is a prefix, we can either use a prefix tree, a Trie, or use the in-built python method startswith().

Let us discuss both solutions starting with the method using Trie. A Trie works by treating the leftmost letter as the root and every subsequent letter as child nodes. So to check if a path is a prefix, we can see if it fits into the tree using dfs.

We first initiate a class of TrieNodes with attributes children as a dictionary and isEnd to mark if we have reach the end of a string.

class TrieNode:
  def __init__(self):
    self.children = {}
    self.isEnd = False

class Solution:
  def removeSubfolders(self, folder: List[str]) -> List[str]:
    root = TrieNode()
    
    for f in folder:
      current = root
      for path in f.split("/"):
        if path:
          if path not in current.children:
            current.children[path] = TrieNode()
          current = current.children[path]
      current.isEnd = True

Then we perform dfs. The dfs works by attempting to construct a possible prefix given the start node. If we succeed then we know we have a proper parent directory.

def dfs(node, path):
  if node.isEnd:
    result.append(path)
    return
  for part, child in node.children.items():
     dfs(child, path + "/" + part)
    

dfs(root, "")
return result

The time complexity is O(n * m) where n is the number of folder paths and m is the average length of the folder paths. This complexity is due to having to create the Trie which involves traversing each folder path and creating the child nodes.

The space complexity is O(n * m) as well as we store every path and its children node in the Trie.

Now, let us discuss the method using python's startswith() method.

We first sort the folders to ensure that parent paths always come before potential child paths.

Then we can check if the previous path is a prefix of the current path. If it is not, then we have a distinct path to append to the result array. If it is, we ignore and continue.

def removeSubfolders(self, folder: List[str]) -> List[str]:
    result = []
    folder.sort()
    prev = ""
    for f in folder:
      if not f.startswith(prev + "/") or not prev:
        result.append(f)
        prev = f
    return result

The time complexity is O(n) as we traverse the folder paths once.

The space complexity is O(n) as we store potentially all n of the folder paths.

The full solutions for both methods can be found near the top of the page.