Remove Sub-Folders from the Filesystem

Leetcode Problem:

• Remove Sub-Folders from the Filesystem

Summary

• Given a list of folders, return the folders after removing all sub-folders in those folders.

Approach

• The approach used is to create a Trie data structure to store the folders
• Each folder is inserted into the Trie by traversing the nodes based on the characters in the folder path
• Then, a traversal is performed on the Trie to find all the top-level folders (i.e., the ones that do not have any sub-folders).

Complexity

• O(N), where N is the total number of characters in all the folder paths.

Explanation

• The solution first inserts all the folder paths into the Trie
• Then, it performs a traversal on the Trie to find all the top-level folders
• The traversal is done recursively, and it checks each node in the Trie to see if it has any sub-folders
• If a node has no sub-folders, it is added to the result vector
• The time complexity of this solution is O(N), where N is the total number of characters in all the folder paths
• This is because each character in the folder paths is visited once during the insertion and traversal operations.

Solution Code:

struct _node{
    bool tail;
    _node* next[27];
    _node(){
        tail = false;
        for(int i = 0 ; i< 27;i++){
            next[i] = nullptr;
        }
    }
};




class Solution {
public:
    _node trie;
    void insert(string s){
        _node* ptr = ≜
        for (char c : s){

            int idx = c == '/' ? 26 : c - 'a';
            if(ptr->next[idx] == nullptr){
                ptr->next[idx] = new _node();
            }
            ptr = ptr->next[idx];
        }
        ptr->tail = true;
    }
    void traversal(_node* root, string s, vector& ans){
        if (root == nullptr) return;
        for(int i = 0; i < 26; i++){
            traversal(root->next[i],s + ""+(char)('a'+i), ans);
        }
        if (root->tail){
            ans.push_back(s);
            return;
        }
        traversal(root->next[26],s + "/", ans);
    }
    vector removeSubfolders(vector& folder) {
        for(string s : folder){
            insert(s);
        }
        vector ans;
        traversal(&trie, "", ans);
        return ans;
    }
};