1233. Remove Sub-Folders from the Filesystem

Given a list of folders folder, return the folders after removing all sub-folders in those folders. You may return the answer in any order.

If a folder[i] is located within another folder[j], it is called a sub-folder of it.

The format of a path is one or more concatenated strings of the form: ‘/‘ followed by one or more lowercase English letters.

• For example, “/leetcode” and “/leetcode/problems” are valid paths while an empty string and “/“ are not.

c++

struct Trie {
    unordered_map<string, Trie*> next;
    bool eof = false;
    string path = "";
    Trie() {};
    
    string parse(string& s, int& p) {
        string res = "";
        while(s.length() > p and s[p] != '/') {
            res.push_back(s[p++]);
        }
        p++;
        return res;
    }
    void insert(string& s, int& p) {
        if(p >= s.length()) eof = true, path = s;
        else {
            auto token = parse(s,p);
            if(!next.count(token)) next[token] = new Trie();
            next[token]->insert(s, p);
        }
    }
    
    void query(vector<string>& res) {
        if(eof) res.push_back(path);
        else {
            for(auto& [_, t] : next)
                t->query(res);
        }
    }
};

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        Trie* t = new Trie();
        for(auto& f : folder) {
            int p = 0;
            t->insert(f,p);
        }
        vector<string> res;
        t->query(res);
        
        return res;
    }
};