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