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.
A:
锻炼了Trie 的写法。
class Solution { public: vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) { sort(products.begin(), products.end()); buildTrie(products); vector<vector<string>> res; Trie* runner = root; for (char ch : searchWord) { vector<string> curLine; if(runner){ runner = runner->children[ch - 'a']; } if (runner) { // if we found existing for (int i = 0; i < min(3, (int)runner->words.size()); i++) { curLine.push_back(runner->words[i]); } } res.push_back(curLine); } return res; } private: struct Trie { vector<Trie*> children=vector<Trie*>(26, nullptr);//CANNOT use children(26,nullptr) vector<string> words; }; Trie* root; void buildTrie(vector<string>& products) { root = new Trie(); for (auto& word : products) { Trie* pre = root; for (char ch : word) { if (not pre->children[ch-'a']) { pre->children[ch-'a'] = new Trie(); } pre = pre->children[ch - 'a']; pre->words.push_back(word); } } } };
Mistakes:
1: 很诡异地,出现了结果的前面为空,后面不为空的结果。TNND。 研究了大半个小时,发现是:
if(runner->childre[ch-'a'] ) 这里的逻辑是:只有为不为空的时候,我们才往下走。 然而应该是已经为 runner 已经为nullptr 了。
所有应该是先往下指, 再看看是不是可以null。
我一开始把2个并到一起去了。
No comments:
Post a Comment