Leetcode 1268: Search Suggestions System

https://leetcode.com/problems/search-suggestions-system/description/

Notes:

This question can be solved without Trie.

We just need to find the sorted strings with the same prefix. So it is pretty straightforward after sorting the strings.

See the code below:

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        int n = searchWord.size();
        vector<vector<string>> res(n);
        sort(products.begin(), products.end());
        for(int i=0; i<n; ++i) {
            string w = searchWord.substr(0, i+1);
            auto it = lower_bound(begin(products), end(products), w);
            for(; it != end(products) && it->substr(0, i+1) == w && res[i].size() < 3; ++it){
                res[i].push_back(*it);
            }
        }
        return res;
    }
};

The above code has a time complexity of O(nlogn), space complexity of O(1).

Another way is that we can use a hash map to record the string with the same prefix. Then we just need to choose the first three strings at each specific prefix.

See the code below:

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        vector<vector<string>> res;
        unordered_map<string, multiset<string>> mp;
        for(auto &a : products) {
            for(int i=0; i<a.size(); ++i) {
                string b = a.substr(0, i+1);
                mp[b].insert(a);
            }
        }
        for(int i=0; i<searchWord.size(); ++i) {
            string key = searchWord.substr(0, i+1);
            res.push_back(vector<string>(mp[key].begin(), mp[key].size()<3 ? mp[key].end() : next(mp[key].begin(), 3)));
        }
        return res;
    }
};