# Easy Cpp Trie Solution

#1
``````#include <bits/stdc++.h>
using namespace std;

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

class Node {
public:
char data;
unordered_map<char, Node*> children;
bool terminal;

Node (char data) {
this -> data = data;
terminal = false;
}
};

class Trie {
Node* root;
int count = 0;
public:
Trie () {
root = new Node('\0');
count = 0;
}

void insert (string str) {
Node* temp = root;
for (auto ch : str) {
if (temp -> children.count(ch) != 0) {
temp = temp -> children[ch];
} else {
Node* newNode = new Node(ch);
temp -> children[ch] = newNode;
temp = newNode;
}
}
temp -> terminal = true;
}

bool find (string str) {
Node* temp = root;
for (auto ch : str) {
if (temp -> children.count(ch) != 0) {
temp = temp -> children[ch];
} else {
return false;
}
}
return temp -> terminal;
}
};

vector<int> Solution::solve(string A, vector<string> &B) {
// Input is a string with words seperated by : '_'
A += '_';
Trie t;
string str = "";
for (auto ch : A) {
if (ch == '_') {
t.insert(str);
str = "";
} else {
str += ch;
}
}

vector <pair <int, int> > v;
int idx = 0;
str = "";
for (auto b : B) {
int count = 0;
str = "";
int len = b.length();
int ch_count = 0;
for (auto ch : b) {
ch_count += 1;
if (ch_count == len) {
str += ch;
if (t.find(str)) {
// cout << str << "\n";
count += 1;
}
str = "";
} else if (ch == '_') {
if (t.find(str)) {
// cout << str << "\n";
count += 1;
}
str = "";
} else {
str += ch;
}
}
// cout << b << " " << str << " " << count << "\n";
v.push_back({count, idx});
idx += 1;
}

// sort (v.begin(), v.end(), greater<pair<int, int> > ());

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

vector <int> ans;

for (auto p : v) {
ans.push_back(p.second);
}

return ans;
}
``````