Answer using tries


#1

struct TrieNode
{
struct TrieNode *children[26];
bool end;
};
struct TrieNode *getNode(void)
{
struct TrieNode *Node = new TrieNode;

Node->end = false; 

for (int i = 0; i < 26; i++) 
    Node->children[i] = NULL; 

return Node; 

}
void insert(struct TrieNode *root, string key)
{
struct TrieNode *crawl = root;

for (int i = 0; i < key.length(); i++) 
{ 
    int index = key[i] - 'a'; 
    if (!crawl->children[index]) 
        crawl->children[index] = getNode(); 

    crawl = crawl->children[index]; 
} 
crawl->end = true; 

}
bool search(struct TrieNode *root, string key)
{
struct TrieNode *crawl = root;

for (int i = 0; i < key.length(); i++) 
{ 
    int index = key[i] - 'a'; 
    if (!crawl->children[index]) 
        return false; 

    crawl = crawl->children[index]; 
} 

return (crawl != NULL && crawl->end); 

}
bool compare(pair<int, int> a, pair<int, int> b)
{
if( a.first > b.first) return true;
else if( a.first < b.first) return false;
else{
if( a.second < b.second) return true;
else return false;
}
}
vector Solution::solve(string a, vector &b) {
struct TrieNode* root=getNode();
for(int i=0; i<a.size(); i++){
string temp;
while( i<a.size() and a[i] != ‘’) temp += a[i], i++;
insert(root,temp);
}
vector<pair<int, int> > v;
for(int i=0; i<b.size(); i++){
int ans = 0;
for(int j=0; j<b[i].size(); j++){
string temp;
while( j<b[i].size() and b[i][j]!= '
’) temp += b[i][j], j++;
if(search(root,temp)) ans++;
}
v.push_back({ans, i});
}
sort(v.begin(), v.end(), compare );
vector ans;
for(int i=0; i<v.size(); i++){
ans.push_back(v[i].second);
}
return ans;
}