# Easy Trie Solution for Hotel Reviews

#1
``````class Node {
public:
bool terminal;
char curr;
unordered_map<char, Node*> children;

Node(char c){
curr = c;
terminal = false;
}
};

class Trie {
public:
Node* root;

Trie() {
root = new Node('\0');
}

void insert(string s) {
Node* it = root;

for(auto c : s){
if(it->children.count(c)){
it = it->children[c];
}else{
Node* n = new Node(c);
it->children[c] = n;
it = n;
}
}

it->terminal = true;
}

bool search(string s){
Node* it = root;
for(char c : s){
if(it->children.count(c)){
it = it->children[c];
}else{
return false;
}
}

return it->terminal;
}
};

Trie generateCoolWords(string s){
Trie T;
string word = "";
for(auto c  : s){
if(c == '_'){
T.insert(word);
word = "";
}else{
word+= c;
}
}
T.insert(word);
return T;
}

int countCoolWords(string s, Trie& T){
string word = "";
int count = 0;
for(auto c  : s){
if(c == '_'){
if(T.search(word)){
count++;
}
word = "";
}else{
word+= c;
}
}
if(T.search(word)){
count++;
}

return count;
}

bool compare(pair<int, int> a , pair<int, int> b){
if(a.first == b.first) return a.second < b.second;

return a.first > b.first;
}

vector<int> Solution::solve(string A, vector<string> &B) {
Trie T = generateCoolWords(A);
vector<pair<int, int>> v;

for(int i = 0; i < B.size(); i++){
v.push_back(make_pair(countCoolWords(B[i], T), i));
}

sort(v.begin(), v.end(), compare);

vector<int> ans;
for(auto e : v){
ans.push_back(e.second);
}

return ans;
}
``````