题目描述
给你一个产品数组 products 和一个字符串 searchWord ,products 数组中每个产品都是一个字符串。
请你设计一个推荐系统,在依次输入单词 searchWord 的每一个字母后,推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个,请按字典序返回最小的三个。
请你以二维列表的形式,返回在输入 searchWord 每个字母后相应的推荐产品的列表。
样例
示例 1:
输入:products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
输出:[
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
解释:按字典序排序后的产品列表是 ["mobile","moneypot","monitor","mouse","mousepad"]
输入 m 和 mo,由于所有产品的前缀都相同,所以系统返回字典序最小的三个产品 ["mobile","moneypot","monitor"]
输入 mou, mous 和 mouse 后系统都返回 ["mouse","mousepad"]
示例 2:
输入:products = ["havana"], searchWord = "havana"
输出:[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
示例 3:
输入:products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
输出:[["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]
示例 4:
输入:products = ["havana"], searchWord = "tatiana"
输出:[[],[],[],[],[],[],[]]
提示:
1 <= products.length <= 1000
1 <= Σ products[i].length <= 2 * 10^4
products[i] 中所有的字符都是小写英文字母。
1 <= searchWord.length <= 1000
searchWord 中所有字符都是小写英文字母。
算法1
据大佬们说 有什么前缀树的解答
我想了想用trie树的方案 没结果
就开始硬怼了。
首先在products 按照字典序排序,然后另开数组记录对应的单词 与 搜索单词相同的字母数
再遍历这个记录相同字母数的数组 找到相同一个单字的词汇 找到相同两个单字的词汇。。。。。。
遍历或者找到或者找不到为空, 中途剪枝为如果找到符合要求的3个词汇也提前退出(由于已经按照字典序排序,最开始找到的符合要求的3个词汇肯定是字典序优先的)
C++ 代码
class Solution {
public:
vector<vector<string>> ret;
int GetsameCharCount(const string& target,const string& src){
int ret =0;
for(int i=0;i < target.size() && i < src.size();i++ ){
if(target[i] == src[i]) ret++;
else{
break;
}
}
return ret;
}
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
sort(products.begin(),products.end());
vector<int> sameCharCount;
for(int i = 0; i < products.size();i++){
int t = GetsameCharCount(products[i],searchWord);
sameCharCount.push_back(t);
}
for(int i = 0; i < searchWord.size();i++){
vector<string> v;
for(int j = 0; j < sameCharCount.size();j++){
if(sameCharCount[j] >i){
v.push_back(products[j]);
}
if(v.size() == 3) break;
}
ret.push_back(v);
}
return ret;
}
};
这题我用前缀树+dfs写过了,虽然感觉有点傻傻的。
是的 开始拿到手感觉可以使用trie树 但是感觉似乎速度上没有优势。
我们只是需要每个单词同搜索单词的相同char的个数,我的写法如果使用二分进行定位 估计可以速度再快点。
那么trie树的构造 查找等速度都显得比较慢了
确实