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;
}