A very easy Trie Solution


#1

struct Node
{
bool endWord;
Node* ch[26];
Node()
{
endWord=false;
for(int i=0;i<26;i++)
ch[i]=NULL;
}
};
void insert(Node* root,string key)
{
Node* p=root;
for(int i=0;i<key.length();i++)
{
if(p->ch[key[i]-‘a’]==NULL)
p->ch[key[i]-‘a’]=new Node();
p=p->ch[key[i]-‘a’];
}
p->endWord=true;
}
int search(Node* root,string key)
{
Node* p=root;

for(int i=0;i<key.length();i++)
{
    if(p->ch[key[i]-'a']==NULL)
    return false;
    p=p->ch[key[i]-'a'];
}
return (p!=NULL && p->endWord);

}

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

vector Solution::solve(string A, vector &B) {
Node* root=new Node();
string word="";
for(int i=0;i<A.length();i++)
{
if(A[i]==’’ && word!="")
{
insert(root,word);
word="";
}
else
word+=A[i];
}
insert(root,word);
word="";
vector<pair<int,int>> ans;
for(int i=0;i<B.size();i++)
{
int count=0;
for(int j=0;j<B[i].length();j++)
{
if(B[i][j]==’
’ && word!="")
{
if(search(root,word))
count++;

            word="";
        }
        else
        word+=B[i][j];
    }
    if(search(root,word))
    count++;
    
    word="";
    ans.push_back({i,count});
}

sort(ans.begin(),ans.end(),mycomp);

vector<int> res;
for(auto x : ans)
res.push_back(x.first);

return res;

}