[LeetCode] 642. Design Search Autocomplete System 設(shè)計(jì)搜索自動(dòng)補(bǔ)全系統(tǒng)

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'). For each character they type except '#', you need to return the top 3historical hot sentences that have prefix the same as the part of sentence already typed. Here are the specific rules:

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

Your job is to implement the following functions:

The constructor function:

AutocompleteSystem(String[] sentences, int[] times): This is the constructor. The input is historical data. Sentences is a string array consists of previously typed sentences. Times is the corresponding times a sentence has been typed. Your system should record these historical data.

Now, the user wants to input a new sentence. The following function will provide the next character the user types:

List<String> input(char c): The input c is the next character typed by the user. The character will only be lower-case letters ('a' to 'z'), blank space (' ') or a special character ('#'). Also, the previously typed sentence should be recorded in your system. The output will be the top 3 historical hot sentences that have prefix the same as the part of sentence already typed.

Example:
Operation: AutocompleteSystem(["i love you", "island","ironman", "i love leetcode"], [5,3,2,2]) 
The system have already tracked down the following sentences and their corresponding times: 
"i love you" : 5 times 
"island" : 3 times 
"ironman" : 2 times 
"i love leetcode" : 2 times 
Now, the user begins another search: 

Operation: input('i') 
Output: ["i love you", "island","i love leetcode"] 
Explanation: 
There are four sentences that have prefix "i". Among them, "ironman" and "i love leetcode" have same hot degree. Since ' ' has ASCII code 32 and 'r' has ASCII code 114, "i love leetcode" should be in front of "ironman". Also we only need to output top 3 hot sentences, so "ironman" will be ignored. 

Operation: input(' ') 
Output: ["i love you","i love leetcode"] 
Explanation: 
There are only two sentences that have prefix "i ". 

Operation: input('a') 
Output: [] 
Explanation: 
There are no sentences that have prefix "i a". 

Operation: input('#') 
Output: [] 
Explanation: 
The user finished the input, the sentence "i a" should be saved as a historical sentence in system. And the following input will be counted as a new search. 

Note:

1. The input sentence will always start with a letter and end with '#', and only one blank space will exist between two words.
2. The number of complete sentences that to be searched won't exceed 100. The length of each sentence including those in the historical data won't exceed 100.
3. Please use double-quote instead of single-quote when you write test cases even for a character input.
4. Please remember to RESET your class variables declared in class AutocompleteSystem, as static/class variables are persisted across multiple test cases. Please see here for more details.

這道題讓實(shí)現(xiàn)一個(gè)簡(jiǎn)單的搜索自動(dòng)補(bǔ)全系統(tǒng)，當(dāng)我們用谷歌或者百度進(jìn)行搜索時(shí)，會(huì)有這樣的體驗(yàn)，輸入些單詞，搜索框會(huì)彈出一些以你輸入為開(kāi)頭的一些完整的句子供你選擇，這就是一種搜索自動(dòng)補(bǔ)全系統(tǒng)。根據(jù)題目的要求，補(bǔ)全的句子是按之前出現(xiàn)的頻率排列的，高頻率的出現(xiàn)在最上面，如果頻率相同，就按字母順序來(lái)顯示。輸入規(guī)則是每次輸入一個(gè)字符，然后返回自動(dòng)補(bǔ)全的句子，如果遇到井字符，表示完整句子結(jié)束。那么肯定需要一個(gè) HashMap，建立句子和其出現(xiàn)頻率的映射，還需要一個(gè)字符串 data，用來(lái)保存之前輸入過(guò)的字符。在構(gòu)造函數(shù)中，給了一些句子，和其出現(xiàn)的次數(shù)，直接將其加入 HashMap，然后 data 初始化為空字符串。在 input 函數(shù)中，首先判讀輸入字符是否為井字符，如果是的話，那么表明當(dāng)前的 data 字符串已經(jīng)是一個(gè)完整的句子，在 HashMap 中次數(shù)加1，并且 data 清空，返回空集。否則的話將當(dāng)前字符加入 data 字符串中，現(xiàn)在就要找出包含 data 前綴的前三高頻句子了，使用優(yōu)先隊(duì)列來(lái)做，設(shè)計(jì)的思路是，始終用優(yōu)先隊(duì)列保存頻率最高的三個(gè)句子，應(yīng)該把頻率低的或者是字母順序大的放在隊(duì)首，以便隨時(shí)可以移出隊(duì)列，所以應(yīng)該是個(gè)最小堆，隊(duì)列里放句子和其出現(xiàn)頻率的 pair 對(duì)兒，并且根據(jù)其頻率大小進(jìn)行排序，要重寫(xiě)優(yōu)先隊(duì)列的 comparator。然后遍歷 HashMap 中的所有句子，首先要驗(yàn)證當(dāng)前 data 字符串是否是其前綴，沒(méi)啥好的方法，就逐個(gè)字符比較，用標(biāo)識(shí)符 matched，初始化為 true，如果發(fā)現(xiàn)不匹配，則 matched 標(biāo)記為 false，并 break 掉。然后判斷如果 matched 為 true 的話，說(shuō)明 data 字符串是前綴，那么就把這個(gè) pair 加入優(yōu)先隊(duì)列中，如果此時(shí)隊(duì)列中的元素大于三個(gè)，那把隊(duì)首元素移除，因?yàn)槭亲钚《?，所以頻率小的句子會(huì)被先移除。然后就是將優(yōu)先隊(duì)列的元素加到結(jié)果 res 中，由于先出隊(duì)列的是頻率小的句子，所以要加到結(jié)果 res 的末尾，參見(jiàn)代碼如下：

class AutocompleteSystem {
public:
    AutocompleteSystem(vector<string> sentences, vector<int> times) {
        for (int i = 0; i < sentences.size(); ++i) {
            freq[sentences[i]] += times[i]; 
        }
        data = "";
    }    
    vector<string> input(char c) {
        if (c == '#') {
            ++freq[data];
            data = "";
            return {};
        }
        data.push_back(c);
        auto cmp = [](pair<string, int>& a, pair<string, int>& b) {
            return a.second > b.second || (a.second == b.second && a.first < b.first);
        };
        priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp) > q(cmp);
        for (auto f : freq) {
            bool matched = true;
            for (int i = 0; i < data.size(); ++i) {
                if (data[i] != f.first[i]) {
                    matched = false;
                    break;
                }
            }
            if (matched) {
                q.push(f);
                if (q.size() > 3) q.pop();
            }
        }
        vector<string> res(q.size());
        for (int i = q.size() - 1; i >= 0; --i) {
            res[i] = q.top().first; q.pop();
        }
        return res;
    }
    
private:
    unordered_map<string, int> freq;
    string data;
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/642

類似題目：

Implement Trie (Prefix Tree)

Top K Frequent Words

參考資料：

https://leetcode.com/problems/design-search-autocomplete-system/

https://leetcode.com/problems/design-search-autocomplete-system/discuss/176550/Java-simple-solution-without-using-Trie-(only-use-HashMap-and-PriorityQueue)

https://leetcode.com/problems/design-search-autocomplete-system/discuss/105379/Straight-forward-hash-table-%2B-priority-queue-solution-in-c%2B%2B-no-trie

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(642.設(shè)計(jì)搜索自動(dòng)補(bǔ)全系統(tǒng))的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)設(shè)計(jì)搜索自動(dòng)補(bǔ)全系統(tǒng)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論