Using Trie & stringstream C++


#1
class Trie {
public:
    bool isend;
    vector<Trie*> child;
    
    Trie(){
        isend = false;
        child  = vector<Trie*>(26,NULL);
    }
    
    void insert(string &s){
        auto node = this;
        for(auto i:s){
            int n = i-'a';
            if(!node->child[n]){
                node->child[n] = new Trie();
            }
            node = node->child[n];
        }
        node->isend = true;
        
    }
    
    bool isExist(string &s){
        auto node = this;
        
        for(auto i:s){
            int n = i-'a';
            if(!node->child[n])
                return false;
            node = node->child[n];
        }
        return node->isend;
    }
    
};

int getCount(string &s,auto &trie){
    int count=0;
    istringstream ss(s);
    string w;
    while(getline(ss,w,'_')){
        if(trie->isExist(w))
            count++;
    }
    return count;
}


bool compare(pair<int,int> &p1,pair<int,int> &p2){
    
    if(p1.first == p2.first)
        return p1.second<p2.second;
    return p1.first>p2.first;
}


vector<int> Solution::solve(string s, vector<string> &v) {
    auto trie = new Trie();
    
    istringstream ss(s);
    string w;
    while(getline(ss,w,'_'))
        trie->insert(w);
        
        
    vector<pair<int,int>> help(v.size());
    for(int i=0;i<v.size();i++){
        help[i]={getCount(v[i],trie),i};
        
    }
    
    sort(help.begin(),help.end(),compare);
    
    vector<int> ans(v.size());
    for(int i=0;i<v.size();i++){
        ans[i] = help[i].second;
        
    }
    
    return ans;
    
}