Trie class in C++, and solution


#1

This class is Memory efficient, well defined, has exception-throw guarantee and robust to larger data types

#include<unordered_map>
#include<string>

class Trie{

private:
    bool isLeaf;
    std::unordered_map<char, Trie* > umap;

public:
    Trie(bool isLeaf=false){
        // Constructor

        this->isLeaf=isLeaf;
        this->umap.clear();
    }

    void insert(std::string s){
        // inserts string starting from this Node

        if(s.empty())
            return;
        
        Trie *ptr=this;
        for(unsigned long long int i=0; i<s.size(); i++)
        {
            char c=s.at(i);
            bool cExists=(ptr->umap.find(c)!=ptr->umap.end());
            
            if(!cExists)
                ptr->umap[c] = new Trie();

            ptr = ptr->umap[c];
        }
        ptr->isLeaf=true;
    }

    bool hasString(std::string s){
        // True if Trie Node has string s

        Trie *ptr=this;
        for(unsigned long long int i=0; i<s.size(); i++)
        {
            char c=s.at(i);
            bool cExists=(ptr->umap.find(c)!=ptr->umap.end());
            
            if(!cExists)
                return false;

            ptr = ptr->umap[c];
        }
        return ptr->isLeaf;
    }

    bool haveChildren(){
        // True if Trie Node has children

        for (auto it : this->umap){
            if (it.second != NULL)
                return true;
        }
        return false;
    }

    ~Trie(){

        this->umap.clear();
    }
};

Use it like this:

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

// --------copy paste the above class as it is----
#include<unordered_map>
#include<string>
class Trie{};
// -----

int goodnessOf(Trie* head, string s)
{
    int i=0, n=s.size(), goodnessVal=0;
    while(true)
    {
        int j=i;
        while(j<n && s[j]!='_') j++;

        goodnessVal += (head->hasString(s.substr(i, j-i)) ? 1: 0);
            
        if(j<n)
            i=j+1;
        else
            break;
    }
    return goodnessVal;
}

bool f(pair<int, int> x, pair<int, int> y)
{ 
    if(x.second == y.second)
        return x.first < y.first;
    return (x.second > y.second); 
}

vector<int> Solution::solve(string A, vector<string> &B) 
{
    Trie *gWords=new Trie();

    int i=0, n=A.size();
    while(true)
    {
        int j=i;
        while(j<n && A[j]!='_') j++;

        gWords->insert(A.substr(i, j-i));
            
        if(j<n)
            i=j+1;
        else
            break;
    }
    
    vector<pair<int, int>> v;
    for(int i=0; i<B.size(); i++)
        v.push_back(make_pair(i, goodnessOf(gWords, B[i])));
    delete (gWords);
    
    sort(v.begin(), v.end(), f);
    
    vector<int> ans;
    for(auto it: v)
        ans.push_back(it.first);
    return ans;
}