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.
"/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 '/'.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.
This Python solution sorts the folder paths and iterates through them. It maintains a 'prev' variable to store the last added folder to the results, ensuring we only add a folder if it is not a sub-folder of the previous folder in the result list.
C++
Java
JavaScript
Time Complexity: O(n log n) due to sorting the list. Space Complexity: O(n) for storing the result list.
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.
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.
C++
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.
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Checking Prefix | Time Complexity: O(n log n) due to sorting the list. Space Complexity: O(n) for storing the result list. |
| Approach 2: Using Trie Data Structure | 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. |
Remove Sub-Folders from the Filesystem - Leetcode 1233 - Python • NeetCodeIO • 10,460 views views
Watch 9 more video solutions →Practice Remove Sub-Folders from the Filesystem with our built-in code editor and test cases.
Practice on FleetCode