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 * 1042 <= folder[i].length <= 100folder[i] contains only lowercase letters and '/'.folder[i] always starts with the character '/'.- Each folder name is unique.
## Solution(Python)
```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
```