1268-搜索推荐系统(Search Suggestions System)

原文链接: https://leetcode-cn.com/problems/search-suggestions-system

英文原文

Given an array of strings products and a string searchWord. We want to design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]
After typing mou, mous and mouse the system suggests ["mouse","mousepad"]

Example 2:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Example 3:

Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

Example 4:

Input: products = ["havana"], searchWord = "tatiana"
Output: [[],[],[],[],[],[],[]]

Constraints:

1 <= products.length <= 1000
There are no repeated elements in products.
1 <= Σ products[i].length <= 2 * 10^4
All characters of products[i] are lower-case English letters.
1 <= searchWord.length <= 1000
All characters of searchWord are lower-case English letters.

中文题目

给你一个产品数组 products 和一个字符串 searchWord ，products 数组中每个产品都是一个字符串。

请你设计一个推荐系统，在依次输入单词 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个，请按字典序返回最小的三个。

请你以二维列表的形式，返回在输入 searchWord 每个字母后相应的推荐产品的列表。

示例 1：

输入：products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
输出：[
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
解释：按字典序排序后的产品列表是 ["mobile","moneypot","monitor","mouse","mousepad"]
输入 m 和 mo，由于所有产品的前缀都相同，所以系统返回字典序最小的三个产品 ["mobile","moneypot","monitor"]
输入 mou， mous 和 mouse 后系统都返回 ["mouse","mousepad"]

示例 2：

输入：products = ["havana"], searchWord = "havana"
输出：[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

示例 3：

输入：products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
输出：[["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

示例 4：

输入：products = ["havana"], searchWord = "tatiana"
输出：[[],[],[],[],[],[],[]]

提示：

1 <= products.length <= 1000
1 <= Σ products[i].length <= 2 * 10^4
products[i] 中所有的字符都是小写英文字母。
1 <= searchWord.length <= 1000
searchWord 中所有字符都是小写英文字母。

通过代码

高赞题解

方法一：字典树

由于我们需要将 searchWord 的前缀与 products 中的字符串进行匹配，因此我们可以使用字典树（Trie）来存储 products 中的所有字符串。这样以来，当我们依次输入 searchWord 中的每个字母时，我们可以从字典树的根节点开始向下查找，判断是否存在以当前的输入为前缀的字符串，并找出字典序最小的三个（若存在）字符串。

对于字典树中的每个节点，我们需要额外地存储一些数据来帮助我们快速得到答案。设字典树中的某个节点为 node，从字典树的根到该节点对应的字符串为 prefix，那么我们可以在 node 中使用数组或优先队列，存放字典序最小的三个以 prefix 为前缀的字符串。具体的做法是：当我们在字典树中插入字符串 product 并遍历到节点 node 时，我们将 product 存储在 node 中，若此时 node 中的字符串超过三个，就丢弃字典序最大的那个字符串。这样在所有的字符串都被插入到字典树中后，字典树中的节点 node 就存放了当输入为 prefix 时应该返回的那些字符串。

[sol1]
struct Trie {
    unordered_map<char, Trie*> child;
    priority_queue<string> words;
};

class Solution {
private:
    void addWord(Trie* root, const string& word) {
        Trie* cur = root;
        for (const char& ch: word) {
            if (!cur->child.count(ch)) {
                cur->child[ch] = new Trie();
            }
            cur = cur->child[ch];
            cur->words.push(word);
            if (cur->words.size() > 3) {
                cur->words.pop();
            }
        }
    }
    
public:
    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& ch: searchWord) {
            if (flag || !cur->child.count(ch)) {
                ans.emplace_back();
                flag = true;
            }
            else {
                cur = cur->child[ch];
                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;
    }
};

[sol1]
class Trie:
    def __init__(self):
        self.child = dict()
        self.words = list()

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        def addWord(root, word):
            cur = root
            for ch in word:
                if ch not in cur.child:
                    cur.child[ch] = Trie()
                cur = cur.child[ch]
                cur.words.append(word)
                cur.words.sort()
                if len(cur.words) > 3:
                    cur.words.pop()

        root = Trie()
        for word in products:
            addWord(root, word)
        
        ans = list()
        cur = root
        flag = False
        for ch in searchWord:
            if flag or ch not in cur.child:
                ans.append(list())
                flag = True
            else:
                cur = cur.child[ch]
                ans.append(cur.words)

        return ans

复杂度分析

时间复杂度：$O(\sum L + S)$，其中 $\sum L$ 是所有字符串的长度之和，$S$ 是字符串 searchWord 的长度。在计算时间复杂度时，我们将字符串的平均长度视为常数，即在字典树中存储、比较和丢弃字符串的时间复杂度均为 $O(1)$。
空间复杂度：$O(\sum L)$。

方法二：二分查找

方法一中的字典树需要使用额外的空间。可以发现，字典树实际上是帮助我们完成了排序的工作。如果我们直接将数组 products 中的所有字符串按照字典序进行排序，那么对于输入单词 searchWord 的某个前缀 prefix，我们只需要在排完序的数组中找到最小的三个字典序大于等于 prefix 的字符串，并依次判断它们是否以 prefix 为前缀即可。由于在排完序的数组中，以 prefix 为前缀的字符串的位置一定是连续的，因此我们可以使用二分查找，找出最小的字典序大于等于 prefix 的字符串 products[i]，并依次判断 products[i]，products[i + 1] 和 products[i + 2] 是否以 prefix 为前缀即可。

此外，在我们输入单词 seachWord 中每个字母的过程中，prefix 的字典序是不断增大的。因此在每次二分查找时，我们可以将左边界设为上一次找到的位置 i，而不用从以 0 为左边界，这样可以减少每次二分查找中的查找次数（但不会减少时间复杂度的数量级）。

[sol2]
class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        sort(products.begin(), products.end());
        string query;
        auto iter_last = products.begin();
        vector<vector<string>> ans;
        for (char ch: searchWord) {
            query += ch;
            auto iter_find = lower_bound(iter_last, products.end(), query);
            vector<string> selects;
            for (int i = 0; i < 3; ++i) {
                if (iter_find + i < products.end() && (*(iter_find + i)).find(query) == 0) {
                    selects.push_back(*(iter_find + i));
                }
            }
            ans.push_back(move(selects));
            iter_last = iter_find;
        }
        return ans;
    }
};

[sol2]
class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort()
        query = ""
        iter_last = 0
        ans = list()
        for ch in searchWord:
            query += ch
            iter_find = bisect.bisect_left(products, query, iter_last)
            ans.append([s for s in products[iter_find : iter_find + 3] if s.startswith(query)])
            iter_last = iter_find
        return ans

复杂度分析

时间复杂度：$O\big((\sum L + S) * \log N\big)$，其中 $\sum L$ 是所有字符串的长度之和，$S$ 是字符串 searchWord 的长度，$N$ 是数组 products 的长度。对字符串进行排序的时间复杂度为 $O(\sum L * \log N)$，二分查找进行了 $L$ 次，每次查找的时间复杂度为 $\log N$。虽然方法二的时间复杂度高于方法一，但方法二的常数较小，因此实际运行速度要快于方法一。
空间复杂度：$O(\log N)$，为排序需要的空间复杂度。

统计信息

通过次数	提交次数	AC比率
8652	14746	58.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途