Leetcode 1233: Remove Sub-Folders from the Filesystem
You are given a list of folder paths, where each path represents a folder in the file system. The task is to remove all sub-folders from the list, keeping only the main folders.
Problem
Approach
Steps
Complexity
Input: The input is a list of folder paths. Each path starts with a '/' and may contain one or more sub-folder paths.
Example: folders = ['/home/user/docs', '/home/user', '/home/user/docs/photos', '/home/user/music']
Constraints:
• 1 <= folder.length <= 4 * 10^4
• 2 <= folder[i].length <= 100
• folder[i] contains only lowercase letters and '/'
• Each folder path is unique
Output: The output should be a list of folder paths with all sub-folders removed.
Example: ["/home/user", "/home/user/music"]
Constraints:
• The output should not contain any sub-folder paths.
Goal: The goal is to remove any folder that is a sub-folder of another folder in the list.
Steps:
• Sort the folder paths lexicographically.
• Use a trie structure to store and check for sub-folders.
• Add a folder to the result list only if it is not a sub-folder of any other folder.
Goal: The input contains unique folder paths, and the number of folder paths is between 1 and 40,000.
Steps:
• The input will not contain any duplicate folder paths.
Assumptions:
• Each folder path starts with a '/' and contains valid characters.
• Input: folders = ['/home/user/docs', '/home/user', '/home/user/docs/photos', '/home/user/music']
• Explanation: The folders '/home/user/docs' and '/home/user/docs/photos' are sub-folders of '/home/user', so they are removed. The remaining folders are '/home/user' and '/home/user/music'.
• Input: folders = ['/a/b/c', '/a/b', '/a/c', '/a']
• Explanation: The folders '/a/b/c', '/a/b', and '/a/c' are sub-folders of '/a', so only '/a' remains.
Approach: To solve this problem, we first sort the folder paths lexicographically and then use a trie data structure to remove sub-folders.
Observations:
• Sorting the folder paths lexicographically ensures that sub-folders will appear after their parent folders.
• Using a trie helps efficiently check if a folder is a sub-folder of another.
Steps:
• Sort the folder paths in lexicographical order.
• Iterate through the sorted list and use a trie to check and remove sub-folders.
• If a folder is not a sub-folder, add it to the result list.
Empty Inputs:
• Not applicable, as the input will always contain at least one folder.
Large Inputs:
• The solution should handle up to 40,000 folder paths efficiently.
Special Values:
• Ensure that folder paths are unique, and no folder path starts with an empty string or contains invalid characters.
Constraints:
• The folder paths are guaranteed to be well-formed and unique.
vector<string> removeSubfolders(vector<string>& folder) {
sort(folder.begin(), folder.end());
vector<string> ans;
TrieNode* root = new TrieNode(false);
for(int i = 0; i < folder.size(); i++) {
if(root->add(folder[i]))
ans.push_back(folder[i]);
}
return ans;
}
1 : Function Definition
vector<string> removeSubfolders(vector<string>& folder) {
This is the function definition for `removeSubfolders`. It takes a vector of folder paths and returns a vector with subfolders removed.
2 : Sorting
sort(folder.begin(), folder.end());
The folder paths are sorted in lexicographical order to ensure that the parent folder always appears before its subfolder.
3 : Result Initialization
vector<string> ans;
An empty vector `ans` is initialized to store the folder paths that are not subfolders of others.
4 : Trie Initialization
TrieNode* root = new TrieNode(false);
A new TrieNode `root` is created to serve as the root of the Trie. The `false` parameter indicates that this node does not represent the end of a valid folder path.
5 : Iterating Over Folders
for(int i = 0; i < folder.size(); i++) {
A loop is started to iterate over each folder in the sorted `folder` vector.
6 : Checking for Subfolders
if(root->add(folder[i]))
The function `add` is called on the root TrieNode to check if the current folder is a subfolder of any previously processed folder. If it is not a subfolder, the folder is added to the result.
7 : Adding to Result
ans.push_back(folder[i]);
If the folder is not a subfolder, it is added to the `ans` vector, which will be returned at the end.
8 : Return Statement
return ans;
The function returns the `ans` vector, which contains the folder paths that are not subfolders of any other folder.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The solution primarily depends on sorting the folder paths and checking each folder using the trie structure.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is proportional to the number of folder paths and the trie storage.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus