1268. Search Suggestions System

一開始想不到更快地解, 提示說可以用暴力法時間為O(n²)

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        vector<vector<string>> res;
        sort(products.begin(), products.end());
        for(int i = 1; i <= searchWord.size();i++){
            vector<string> cur_s;
            string s = searchWord.substr(0, i);
            for(auto p: products){
                string compare = p.substr(0, i);
                if(cur_s.size() >= 3) break;
                if(s == compare){
                    cur_s.push_back(p);
                }
            }
            res.push_back(cur_s);
        }
        return res;
    }
};

在看完李哥的解答後, 頭一次知道lower_bound可以這樣用, 只要符合這個字串的前幾個位元都對的話, 就可以鎖定lower_bound

然後接下來因為增加字母, 自然是會一直縮小範圍, 這個方法真的猛

時間複雜度為O(nlogn)

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