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.
1def removeSubfolders(folder):
2 folder.sort()
3 res = []
4 prev = ""
5 for f in folder:
6 if not f.startswith(prev):
7 res.append(f)
8 prev = f + "/"
9 return resThis 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.
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.
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <algorithm>
5using namespace std;
class TrieNode {
public:
unordered_map<string, TrieNode*> children;
bool isEnd;
TrieNode() : isEnd(false) {}
};
void insert(TrieNode* root, const string& path) {
TrieNode* node = root;
istringstream stream(path);
string part;
while (getline(stream, part, '/')) {
if (part.empty()) continue;
if (!node->children.count(part))
node->children[part] = new TrieNode();
node = node->children[part];
if (node->isEnd) return;
}
node->isEnd = true;
}
void collect(TrieNode* node, string path, vector<string>& result) {
if (node->isEnd) {
result.push_back(path);
return;
}
for (auto& [part, child] : node->children) {
collect(child, path + "/" + part, result);
}
}
class Solution {
public:
vector<string> removeSubfolders(vector<string>& folder) {
sort(folder.begin(), folder.end());
TrieNode* root = new TrieNode();
for (const auto& path : folder) {
insert(root, path);
}
vector<string> result;
collect(root, "", result);
return result;
}
};This C++ solution creates a Trie to store folders and their structure. When a path inserted is not a sub-folder, it is marked as an end. Then a DFS traversal gathers all end paths.