Help needed in memory limit exceeded in trie


#1

class Trie
{
private:
struct node
{
node* index[26]={NULL};
int eow=0;
};
node *master;
public:
Trie()
{
master = new node;
}
void insert(string word)
{
auto t=master;
for(auto s:word)
{
if(t->index[s-‘a’]==NULL)
t->index[s-‘a’]= new node;
t=t->index[s-‘a’];
}
t->eow++;
}
bool search(string word)
{
auto t=master;
for(auto s:word)
{
if(t->index[s-‘a’]==NULL)
t->index[s-‘a’] = new node;
t=t->index[s-‘a’];
}
return t->eow!=0;
}
};
int count(string &s,Trie &dic)
{
for(auto &it:s)
{
if(it==’’)
it=’ ‘;
}
stringstream x(s);
string temp;
int ans=0;
while(x>>temp)
{
if(dic.search(temp))
ans++;
}
return ans;
}
bool cmp(pair<int,int> &a,pair<int,int> &b)
{
int cnt1=a.first,cnt2=b.first;
if(cnt1!=cnt2)
return cnt1>cnt2;
return a.second<b.second;
}
vector Solution::solve(string s, vector &v)
{
for(auto &it:s)
if(it==’
’)
it=’ ';
stringstream x(s);
string tstring;
Trie dic;
while(x>>tstring)
{
dic.insert(tstring);
}
vector<pair<int,int>> temp;
int n=v.size();
for(int i=0;i<n;i++)
{
temp.push_back({count(v[i],dic),i});
}
sort(temp.begin(),temp.end(),cmp);
vector ans;
for(int i=0;i<n;i++)
{
ans.push_back(temp[i].second);
}
return ans;
}
I always implement trie in this way and there was never a problem.Please help me.It is showing memory limit exceeded