Problem Description
Given a list of folder paths, remove all folders that are sub-folders of another folder from the list. A folder is considered a sub-folder if it starts with another folder's path followed by a '/'.
Key Insights
- Sorting the folders lexicographically guarantees that any parent folder comes before its sub-folders.
- While iterating through the sorted list, only add a folder to the result if it is not a sub-folder of the previously added folder.
- Checking if a folder is a sub-folder is done by confirming whether the folder string starts with the previous folder string plus a '/'.
Space and Time Complexity
Time Complexity: O(n log n * L) where n is the number of folders and L is the average length of the folder strings (sorting cost and prefix checking). Space Complexity: O(n) for storing the result list.
Solution
The approach starts by sorting the folder list lexicographically so that parent folders come before any of their sub-folders. Then, iterate through each folder in the sorted list. For each folder, check if it is a sub-folder of the last folder added to the result. This is done by verifying that the folder does not start with the previous folder path followed by a '/'. If it does not, add the folder to the result. This method avoids unnecessary comparisons and efficiently filters out sub-folders.