1268.md

1268. Search Suggestions System

Leetcode link

解题思路

本题要求我们实现一个搜索推荐系统，要求输入每一个字符都要展示前三个搜索结果（字典序排序）

这种逐个字符搜索的题目很适合使用 字典树 来求解，对于字典树中任意一个 node 节点，从根节点到它的字符串称为 prefix

另外，因为要逐个展示搜索结果，所以我们需要额外使用一个优先队列来保存三个以当前 prefix 为开头的字符串

C++

// 字典树结构
struct Trie {
    unordered_map<char, Trie*> child;
    priority_queue<string> words;
};

class Solution {
public:
    void addWord(Trie* root, const string& word) {
        Trie* cur = root;
        for(const char& c : word) {
            if(!cur->child.count(c)) {
                cur->child[c] = new Trie();
            }
            cur = cur->child[c];
          // 额外维护一个优先队列保存当前 prefix 的前三个字符串
            cur->words.push(word);
            if(cur->words.size() > 3) {
                cur->words.pop();
            }
        }
    }
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        Trie* root = new Trie();
        for(const string& word: products) {
            addWord(root, word);
        }
        
        vector<vector<string>> ans;
        Trie* cur = root;
        // 标记字典树的结尾
        bool flag = false;
        
        for(const char& c: searchWord) {
            if(flag || !cur->child.count(c)) {
                ans.push_back({});
                flag = true;
            } else {
                cur = cur->child[c];
                vector<string> selects;
                while(!cur->words.empty()) {
                    selects.push_back(cur->words.top());
                    cur->words.pop();
                }
                reverse(selects.begin(), selects.end());
                ans.push_back(move(selects));
            }
        }
        
        return ans;
    }
};