nikunjsoni

642

Jun 26th, 2021
92
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class AutocompleteSystem {
  2.    
  3.     class TrieNode{
  4.         public:
  5.             unordered_map<char, TrieNode*> child;
  6.             string str;
  7.             int count;
  8.             TrieNode(): str(""), count(0) {}
  9.     };
  10.    
  11.     void insert(string& s, TrieNode* root, int times){
  12.         TrieNode* curr = root;
  13.         for (int i=0;i<s.size();i++){
  14.             if (!curr->child.count(s[i]))
  15.                 curr->child[s[i]] = new TrieNode();
  16.             curr = curr->child[s[i]];
  17.         }
  18.         curr->count += times;
  19.         curr->str = s;
  20.     }
  21.    
  22. public:
  23.     void dfs(TrieNode* temp){
  24.         if (temp->str != "") q.push({temp->str, temp->count});
  25.         for (auto& ele: temp->child){
  26.             dfs(ele.second);
  27.         }
  28.     }
  29.    
  30.     struct comp{
  31.         bool operator() (pair<string, int>& a, pair<string, int>& b){
  32.             return a.second<b.second || a.second==b.second && a.first>b.first;
  33.         }
  34.     };
  35.    
  36.     priority_queue<pair<string, int>, vector<pair<string, int> >, comp> q;
  37.        
  38.     TrieNode* root, *curr;
  39.     AutocompleteSystem(vector<string> sentences, vector<int> times) {
  40.         root = new TrieNode();
  41.         for (int i=0;i<sentences.size();i++){
  42.             insert(sentences[i], root, times[i]);
  43.         }
  44.         curr = root;
  45.     }
  46.    
  47.    
  48.     string s="";
  49.     vector<string> input(char c) {
  50.         q = priority_queue<pair<string, int>, vector<pair<string, int> >, comp>();
  51.         if (c=='#'){
  52.             insert(s, root, 1);
  53.             s="";
  54.             curr = root; //start searching from the beginning node for the next sentence
  55.             return {};
  56.         }
  57.         s += c;
  58.         if (curr && curr->child.count(c)){
  59.             curr = curr->child[c];
  60.         }else{
  61.             curr = NULL; //curr node is null so empty result for any further characters in current input
  62.             return {};
  63.         }
  64.        
  65.         if (curr->str != "") q.push({curr->str, curr->count});
  66.         for (auto& ele: curr->child){
  67.             dfs(ele.second);
  68.         }
  69.        
  70.         vector<string> res;
  71.         while (!q.empty() && res.size()<3){
  72.             res.push_back(q.top().first);
  73.             q.pop();
  74.         }
  75.        
  76.         return res;
  77.     }
  78. };
  79.  
RAW Paste Data