1268. Search Suggestions System**

https://leetcode.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.

C++ 实现 1

先介绍最暴力的解法, 虽然慢一些, 但是能解决问题…

对 products 排序, 然后判断 searchWord 中的每个 prefix, 是否存在于当前访问的 products[j] 中, 如果存在, 那就加入到 candidates 中, 并保证 candidates 的数量不超过 3. 时间复杂度为 $O(N^2)$

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        std::sort(products.begin(), products.end());
        vector<vector<string>> res;
        for (int i = 0; i < searchWord.size(); ++ i) {
            vector<string> candidates;
            for (int j = 0; j < products.size(); ++ j) {
                if (products[j].find(searchWord.substr(0, i + 1)) == 0) {
                    if (candidates.size() == 3) break;
                    candidates.push_back(products[j]);
                } 
            }
            res.push_back(candidates);
        }
        return res;
    }
};

C++ 实现 2

来自: [C++/Java/Python] Sort and Binary Search the Prefix

使用二分法来查找 prefix. 具体原理是, 对于一个已经排序好的字符串序列 A, 如果 A[i] 是 A[j] 的 prefix, 那么 A[i] 肯定也是 {A[i], A[i+1], ..., A[j]} 中所有元素的 prefix. 这样的话, 问题就转换为在已排序序列 A 中查找 prefix (这个 prefix 属于 searchWord) 的 lower_bound (即第一个大于或等于 prefix 的元素).

当找到 lower_bound 时, 从 lower_bound 开始判断后 3 个数据是否满足条件.

class Solution {
public:
	vector<vector<string>> suggestedProducts(vector<string>& A, string searchWord) {
        auto it = A.begin();
        sort(it, A.end());
        vector<vector<string>> res;
        string cur = "";
        for (char c : searchWord) {
            cur += c;
            vector<string> suggested;
            it = lower_bound(it, A.end(), cur);
            for (int i = 0; i < 3 && it + i != A.end(); i++) {
                string& s = *(it + i);
                if (s.find(cur) != 0) break;
                suggested.push_back(s);
            }
            res.push_back(suggested);
        }
        return res;
    }
};