Getting WA in this trie Question Please Help


#1


Please Help

Blockquote
struct trienode{
struct trienode* child[26];
bool isleaf;
};
struct trienode* nwtrienode()
{
trienode* t=new trienode();
for(int i=0;i<26;i++)
t->child[i]=NULL;
t->isleaf=false;
return t;
}

void insert(string g,trienode* &t)
{
trienode* prt=t;
for(int i=0;i<g.length();i++)
{
if(!prt->child[g[i]-‘a’])
prt->child[g[i]-‘a’]=nwtrienode();
prt=prt->child[g[i]-‘a’];
}
prt->isleaf=true;
}

bool search(string g,trienode* t)
{
trienode* prt=t;
for(int i=0;i<g.length();i++)
{
if(!prt->child[g[i]-‘a’])
return false;
prt=prt->child[g[i]-‘a’];
}
if(prt->isleaf)
return true;
return false;
}
bool comp(std::pair<int, int> lhs, std::pair<int, int> rhs) {
if (lhs.first > rhs.first) {
return true;
}
else if (lhs.first == rhs.first) {
return lhs.second < rhs.second;
}
}
vector Solution::solve(string A, vector &B) {
trienode* t=nwtrienode();
for(int i=0;i<A.size();i++)
{
string g="";
int j=i;
while(j<A.size()&&A[j]!=’’)
{
g+=A[j];
j++;
}
i=j;
insert(g,t);
}
vector cnt(B.size(),0);
for(int i=0;i<B.size();i++)
{
for(int j=0;j<B[i].length();j++)
{
string g="";
int k=j;
while(k<B[i].length()&&B[i][k]!=’
’)
{
g+=B[i][k];
k++;
}
j=k;
// cout<<g<<endl;
if(search(g,t))
cnt[i]++;
}
}
vector<pair<int,int>> a;
for(int i=0;i<B.size();i++)
{
a.push_back({cnt[i],i});
}
sort(a.begin(),a.end(),comp);
vector t1;
for(int i=0;i<B.size();i++)
t1.push_back(a[i].second);
return t1;
}