642. Design Search Autocomplete System

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character ‘#’).

You are given a string array sentences and an integer array times both of length n where sentences[i] is a previously typed sentence and times[i] is the corresponding number of times the sentence was typed. For each input character except ‘#’, return the top 3 historical hot sentences that have the same prefix as the part of the sentence already typed.

Here are the specific rules:

• The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
• The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same hot degree, use ASCII-code order (smaller one appears first).
• If less than 3 hot sentences exist, return as many as you can.
• When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.

Implement the AutocompleteSystem class:

• AutocompleteSystem(String[] sentences, int[] times) Initializes the object with the sentences and times arrays.
• List input(char c) This indicates that the user typed the character c.

• Returns an empty array [] if c == ‘#’ and stores the inputted sentence in the system.
• Returns the top 3 historical hot sentences that have the same prefix as the part of the sentence already typed. If there are fewer than 3 matches, return them all.

  struct compare {
      bool operator()(pair<int, string> p1, pair<int, string> p2) {
          if(p1.first == p2.first) return p1.second < p2.second;
          return p1.first > p2.first;
      }
  };
  struct Trie {
      Trie* next[128];
      priority_queue<pair<int, string>, vector<pair<int, string>>, compare> pq;
      unordered_map<string, int> history;
  public:
      Trie() {
          memset(next, 0, sizeof(next));
      }
      void rebalance(string str, int time) {
          unordered_map<string, int> tmp;
          while(!pq.empty()) {
              auto [time, sentence] = pq.top(); pq.pop();
              tmp.insert({sentence,time});
          }
          tmp[str] = time;
          for(auto [sentence, t] : tmp) {
              pq.push({t, sentence});
          }
          if(pq.size() > 3) pq.pop();
      }
      void insert(string str, int i, int time) {
          if(i != str.length()) {
              if(!next[str[i]]) next[str[i]] = new Trie();
              next[str[i]]->insert(str,i+1,time);
          }
          history[str] += time;
          rebalance(str, history[str]);
      }
      Trie* find(char ch) {
          return next[ch];
      }
      vector<string> get() {
          if(pq.empty()) return {};
          multimap<int, string> tmp;
          vector<string> res;
          while(!pq.empty()) {
              auto [time, sentence] = pq.top(); pq.pop();
              tmp.insert({time,sentence});
              res.push_back(sentence);
          }
          reverse(res.begin(), res.end());
          for(auto [time, sentence]: tmp) {
              pq.push({time, sentence});
          }
          return res;
      }
  };
  class AutocompleteSystem {
      Trie* root;
      Trie* cur;
      string history = "";
  public:
      AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
          root = new Trie();
          for(int i = 0; i < times.size(); i++) {
              root->insert(sentences[i], 0, times[i]);
          }
          cur = root;
      }
  
      vector<string> input(char c) {
          if(c == '#') {
              cur = root;
              root->insert(history, 0, 1);
              history = "";
              return {};
          }
          history += c;
          if(cur == NULL) return {};
          cur = cur->find(c);
          if(cur == NULL) return {};
          return cur->get();
      }
  };
  
  /**
   * Your AutocompleteSystem object will be instantiated and called as such:
   * AutocompleteSystem* obj = new AutocompleteSystem(sentences, times);
   * vector<string> param_1 = obj->input(c);
   */