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.
1#include <vector>
2#include <string>
3#include <algorithm>
4using namespace std;
5
6vector<string> removeSubfolders(vector<string>& folder) {
7 sort(folder.begin(), folder.end());
8 vector<string> res;
9 string prev = "";
10 for (const string& f : folder) {
11 if (f.find(prev) != 0) {
12 res.push_back(f);
13 prev = f + "/";
14 }
15 }
16 return res;
17}This C++ solution sorts the folder list and uses the 'find' method to determine if the current folder is a sub-folder by checking if it starts with the previous added folder plus '/'.
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.