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;
    }
};

解题思路二

当然，因为题目是需要我们找出限定范围内的 products，所以我们可以通过排序+缩小窗口的思路来进一步降低复杂度

步骤如下：

1. 先对 products 按照字典序排序
2. 用两个下标 left，right 分别指向排序后 products 的头尾
3. 对于每一个 searchWord 的字符，我们需要判断 products 中相对位置字符的大小，更新 left 与 right
4. 把确定范围的前三个放入返回的数组 res 中
5. 重复第三步，直到遍历完所有的 searchWord 字符
6. 最后返回 res

Javascript

/**
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
var suggestedProducts = function (products, searchWord) {
    const sLen = searchWord.length
    const pLen = products.length
    products.sort()

    let left = 0
    let right = pLen - 1
    const res = []
    for (let i = 0; i < sLen; i++) {
        const temp = []
        while (left <= right && products[left].charAt(i) < searchWord[i]) {
            left++
        }
        while (right >= 0 && products[right].charAt(i) > searchWord[i]) {
            right--
        }
        for (let j = 0; j < 3 && (left + j) <= right; j++) {
            temp.push(products[left + j])
        }
        res.push(temp)
    }

    return res
};

复杂度分析

M 代表 searchWord 的字符长度；n 代表 products 的长度；l 代表 products 中字符串的平均长度

时间

排序：O(nlogn * l)

双指针窗口遍历：O(n)

searchWord 遍历：O(m)

总复杂度：O(nlogn * l)

空间

O(n)