C++ Trie - easy


#1

‘’’
struct trie{
struct trie children[26];
bool isEnd;
};
struct trie
get_node(void)
{
struct trie *p = new trie;
for(int i =0; i<=26; i++)
{
p->children[i]=NULL;
}
p->isEnd = false;
return p;
}
void insert(trie *root, string word)
{
trie *p = root;
for(int i =0; i<word.size(); i++){
int paul = word[i]-‘a’;
if(p->children[paul]==NULL)
p->children[paul] = get_node();
p = p->children[paul];
}
p->isEnd = true;
}
bool search(trie *root, string word)
{
trie p = root;
for(int i =0; i<word.size(); i++)
{
int paul = word[i]-‘a’;
if(p->children[paul]==NULL)
return false;
p = p->children[paul];
}
return p!=NULL && p->isEnd ;
}
trie build_trie(trie root, string A)
{
string temp="";
for(int i=0; i<A.size(); i++){
if(A[i]==’_’ && temp.size()!=0)
{
insert(root, temp);
temp = “”;
}
else
temp+=A[i];
}
if(temp.size()!=0)
{
insert(root, temp);
temp="";
}
return root;
}
int count_match(trie
root, string word)
{
string temp="";
int count = 0;
for(int i=0; i<word.size(); i++){
if(word[i]==’_’ && temp.size()!=0)
{
// cout<<temp<<" “;
if(search(root, temp))
count++;
temp = “”;
}
else
temp+=word[i];
}
if(temp.size()!=0)
{
// cout<<temp<<” ";

    if(search(root, temp))
    count++;
    temp="";
}
return count;

}
bool mycomp(pair<int, int> a, pair<int, int> b)
{
if(a.first!=b.first)
return a.first>b.first;
return a.second<b.second;
}
vector Solution::solve(string A, vector &B) {

trie *root = get_node();
vector<int> ans;
if(B.empty()) return ans;
root = build_trie(root, A);

vector<pair<int, int>> k;
for(int i = 0; i<B.size(); i++)
{
    string madhu  = B[i];
    int match = count_match(root, madhu);
    // cout<<match<<" ";
    k.push_back({match, i});
}
sort(k.begin(), k.end(), mycomp);

for(int i =0; i<k.size(); i++)
{
    ans.push_back(k[i].second);
}
return ans;

}
‘’’