Update 642.Design-Search-Autocomplete-System.cpp

wisdompeak · web-flow · commit 21c5983222ff · 2022-06-18T23:38:05.000-07:00
diff --git a/Design/642.Design-Search-Autocomplete-System/642.Design-Search-Autocomplete-System.cpp b/Design/642.Design-Search-Autocomplete-System/642.Design-Search-Autocomplete-System.cpp
@@ -1,70 +1,88 @@
-class AutocompleteSystem {
-    unordered_map<string,int>Map;
-    string data;
-    
-    struct cmp
+class TrieNode
+{
+    public:
+    TrieNode* next[128];
+    set<pair<int,string>>top;
+    TrieNode()
     {
-        bool operator()(pair<string,int>a, pair<string,int>b)
-        {
-            if (a.second==b.second)
-                return a.first<b.first;
-            else
-                return a.second>b.second;
-        }
-    };
+        for (int i=0; i<128; i++)
+            next[i] = NULL;        
+    }    
+};
+
+class AutocompleteSystem {    
+    TrieNode* root;
+    string inputStr;
+    TrieNode* cur;
+    int flag = 1;
 public:
-    AutocompleteSystem(vector<string> sentences, vector<int> times) 
+    AutocompleteSystem(vector<string>& sentences, vector<int>& times) 
     {
+        root = new TrieNode();     
+        cur = root;
         for (int i=0; i<sentences.size(); i++)
-            Map[sentences[i]]=times[i];
-        data.clear();
+            add(root, sentences[i], 0, -times[i]);        
+    }
+    
+    void add(TrieNode* node, const string sentence, int i, int freq)
+    {        
+        if (i==sentence.size()) return;
+        
+        int k = sentence[i];
+        if (node->next[k] == NULL)
+            node->next[k] = new TrieNode();
+        node = node->next[k];
+        
+        int f = 0;
+        for (auto iter = node->top.begin(); iter!=node->top.end(); iter=next(iter))
+        {
+            if (iter->second == sentence)
+                f = iter->first;
+        }
+        if (f!=0) node->top.erase({f, sentence});        
+        node->top.insert(make_pair(f+freq, sentence));    
+        
+        add(node, sentence, i+1, freq);
     }
     
     vector<string> input(char c) 
     {
+        inputStr.push_back(c);
+        
         if (c=='#')
         {
-            Map[data]++;
-            data.clear();
+            inputStr.pop_back();
+            add(root, inputStr, 0, -1);
+            inputStr = "";
+            cur = root;
+            flag = 1;
             return {};
         }
-        
-        data.push_back(c);
-        priority_queue<pair<string,int>,vector<pair<string,int>>,cmp>pq;        
-        
-        for (auto x:Map)
+        else if (flag==0)
         {
-            string a=x.first;
-            if (match(data,a))
-            {                
-                pq.push({a,Map[a]});
-                if (pq.size()>3) pq.pop();
-            }
+            return {};
         }
-        
-        vector<string>results;
-        while (!pq.empty())
+        else if (cur->next[c]==NULL)
         {
-            results.push_back(pq.top().first);
-            pq.pop();
+            flag = 0;
+            return {};
         }
-        reverse(results.begin(),results.end());
-        return results;
-    }
-    
-    bool match(string a, string b)
-    {
-        for (int i=0; i<a.size(); i++)
+        
+        cur = cur->next[c];
+        vector<string>rets;
+        for (auto iter = cur->top.begin(); iter!=cur->top.end(); iter=next(iter))
         {
-            if (i>=b.size() || a[i]!=b[i])
-                return false;
+            rets.push_back(iter->second);
+            if (rets.size()==3) break;
         }
-        return true;
+        return rets;
+        
     }
+    
 };
 
 /**
  * Your AutocompleteSystem object will be instantiated and called as such:
- * AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
- * vector<string> param_1 = obj.input(c);
+ * AutocompleteSystem* obj = new AutocompleteSystem(sentences, times);
+ * vector<string> param_1 = obj->input(c);
  */
