1233-remove-sub-folders-from-the-filesystem

Try it on leetcode

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.

 

Example 1:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

Example 2:

Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d" will be removed because they are subfolders of "/a".

Example 3:

Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]

 

Constraints:

• 1 <= folder.length <= 4 * 104
• 2 <= folder[i].length <= 100
• folder[i] contains only lowercase letters and '/'.
• folder[i] always starts with the character '/'.
• Each folder name is unique.

Solution(Python)

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

class Solution:
    def __init__(self):
        self.root = TrieNode()

    def removeSubfolders(self, folder: List[str]) -> List[str]:
        return self.trie_(folder)
    

    # Time Complexity: O(N*L^2)
    # Space Complexity: O(N*L)
    def set_(self, folder: List[str]) -> List[str]:
        folderSet = set(folder)
        result  = []
        for folder in folder:
            isSubFolder = False
            prefix = folder
            while not prefix == "":
                pos = prefix.rfind("/")
                if not pos:
                    break
                prefix = prefix[0:pos]
                if prefix in folderSet:
                    isSubFolder = True
                    break
            if not isSubFolder:
                result.append(folder)
                
        return result

    
    # Time Complexity: O(N*L*logN)
    # Space Complexity: O(N*L)
    def sort_(self, folder: List[str]) -> List[str]:   
        folder.sort()
        result  = []
        for f in  folder:
            if len(result) == 0:
                result.append(f)
                continue
            lastfolder = result[-1]
            lastfolder+="/"
            if not f.startswith(lastfolder):
                result.append(f)
        return result
        
    # Time Complexity: O(N*L)
    # Space Complexity: O(N*L)
    def trie_(self, folder: List[str]) -> List[str]:   
        for path in folder:
            cur_node = self.root
            folders = path.split("/")
            for foldername in folders:
                if foldername == "":
                    continue
                if foldername not in cur_node.children:
                    cur_node.children[foldername] = TrieNode()
                cur_node = cur_node.children[foldername]
            cur_node.isEndOfFolder = True
        
        result = []

        for path in folder:
            current_node = self.root
            folders = path.split("/")
            is_subfolder = False

            for i, folder_name in enumerate(folders):
                if folder_name == "":
                    continue
                next_node = current_node.children[folder_name]
                # Check if the current folder path is a subfolder of an existing folder
                if next_node.isEndOfFolder and i != len(folders) - 1:
                    is_subfolder = True
                    break  # Found a subfolder
                current_node = next_node

            # If not a subfolder, add to the result
            if not is_subfolder:
                result.append(path)
        return result