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 <= 10001 <= Σ products[i].length <= 2 * 10^4- All characters of
products[i]are lower-case English letters. 1 <= searchWord.length <= 1000- All characters of
searchWordare lower-case English letters.
Solution 1: Binary Search
Sort the input array and do two binary searches.
One for prefix of the search word as lower bound, another for prefix + ‘~’ as upper bound.
‘~’ > ‘z’
Time complexity: O(nlogn + l * logn)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua, 36ms, 35MB class Solution { public: vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) { vector<vector<string>> ans; std::sort(begin(products), end(products)); string key; for (char c : searchWord) { key += c; auto l = lower_bound(begin(products), end(products), key); auto r = upper_bound(begin(products), end(products), key += '~'); if (l == r) break; // early return key.pop_back(); ans.emplace_back(l, min(l + 3, r)); } while (ans.size() != searchWord.length()) ans.push_back({}); return ans; } }; |
Solution 2: Trie
Initialization: Sum(len(products[i]))
Query: O(len(searchWord))
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
// Author: Huahua, 148 ms, 98.8 MB struct Trie { Trie(): nodes(26) {} ~Trie() { for (auto* node : nodes) delete node; } vector<Trie*> nodes; vector<const string*> words; static void addWord(Trie* root, const string& word) { for (char c : word) { if (root->nodes[c - 'a'] == nullptr) root->nodes[c - 'a'] = new Trie(); root = root->nodes[c - 'a']; if (root->words.size() < 3) root->words.push_back(&word); } } static vector<vector<string>> getWords(Trie* root, const string& prefix) { vector<vector<string>> ans(prefix.size()); for (int i = 0; i < prefix.size(); ++i) { char c = prefix[i]; root = root->nodes[c - 'a']; if (root == nullptr) break; for (auto* word : root->words) ans[i].push_back(*word); } return ans; } }; class Solution { public: vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) { std::sort(begin(products), end(products)); Trie root; for (const auto& product : products) Trie::addWord(&root, product); return Trie::getWords(&root, searchWord); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment