C++ using Trie Data Structure


#1
struct trie{
    struct trie *child[26];
    bool isend;
    trie(){
        memset(child, 0, sizeof(child));
        isend = false;
    }
};
struct trie *root;
void insert(string str){
    struct trie* curr = root;
    for(char ch: str){
        if(curr->child[ch-'a']== nullptr)
            curr->child[ch-'a'] = new trie;
        curr = curr->child[ch-'a'];
    }
    curr->isend = true;
}
int search(string str){
    struct trie *curr = root;
    for(char ch: str){
        if(curr->child[ch-'a']==nullptr)
            return 0;
        curr = curr->child[ch-'a'];
    }
    return curr->isend==true?1:0;
}
bool customCompare(const pair<int,int> &a, const pair<int, int> &b){
    if(a.first!=b.first)
        return a.first>b.first;
    return a.second<b.second;
}
vector<int> Solution::solve(string A, vector<string> &B) {
    string s = "";
    root = new trie;
    for(int i = 0; i<A.length(); i++){
        if(A[i]=='_'){
            insert(s);
            s = "";
            continue;
        }
        s.push_back(A[i]);
    }
    insert(s);
    vector<pair<int,int>> vp;
    for(int i = 0; i<B.size(); i++){
        s = "";
        int cnt = 0;
        for(int j = 0; j<B[i].length(); j++){
            if(B[i][j]=='_'){
                cnt+=search(s);
                s="";
                continue;
            }
            s+=B[i][j];
        }
        cnt+=search(s);
        vp.push_back({cnt, i});
    }
    sort(vp.begin(), vp.end(), customCompare);
    vector<int> ans;
    for(int i = 0; i<vp.size(); i++)
        ans.push_back(vp[i].second);
    return ans;
}