Sponsored
Sponsored
The main idea of this approach is to first sort the folders alphabetically. This way, any sub-folder will appear immediately after its parent folder. We can then iterate through the sorted list and check if the current folder is a prefix of the next folder (followed by '/'). If it is not a prefix, we add it to the final result list.
Time Complexity: O(n log n) due to sorting the list. Space Complexity: O(n) for storing the result list.
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5public class Solution {
6 public List<String> removeSubfolders(String[] folder) {
7 Arrays.sort(folder);
8 List<String> res = new ArrayList<>();
9 String prev = "";
10 for (String f : folder) {
11 if (!f.startsWith(prev)) {
12 res.add(f);
13 prev = f + "/";
14 }
15 }
16 return res;
17 }
18}This Java solution sorts the folder list and iterates through each folder, checking if it starts with the previously added folder (indicating a sub-folder relationship).
In this approach, we use a Trie (or Prefix Tree) to represent the hierarchy of folders. We insert each folder path into the Trie while ensuring to mark the end of any folder. During insertion, if we find that a folder is already marked as the end of a path in the Trie, we ignore any further paths as sub-folders of this path.
Time Complexity: O(n * l) where n is the number of folders, and l is the average length of the folder paths. Space Complexity: O(n * l) for the Trie.
1class TrieNode:
2 def __init__(
This Python solution builds a Trie for all folder paths. It only marks paths as ends when they are not sub-folders, thus ignoring deeper sub-folders in the structure.