题目描述
给你一个产品数组 products
和一个字符串 searchWord
,products
数组中每个产品都是一个字符串。
请你设计一个推荐系统,在依次输入单词 searchWord
的每一个字母后,推荐 products
数组中前缀与 searchWord
相同的最多三个产品。如果前缀相同的可推荐产品超过三个,请按字典序返回最小的三个。
请你以二维列表的形式,返回在输入 searchWord
每个字母后相应的推荐产品的列表。
样例
输入: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"]
输入:products = ["havana"], searchWord = "havana"
输出:[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
输入:products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
输出:[["baggage","bags","banner"],["baggage","bags","banner"],
["baggage","bags"],["bags"]]
输入:products = ["havana"], searchWord = "tatiana"
输出:[[],[],[],[],[],[],[]]
限制
1 <= products.length <= 1000
1 <= Σ products[i].length <= 2 * 10^4
products[i]
中所有的字符都是小写英文字母。1 <= searchWord.length <= 1000
searchWord
中所有字符都是小写英文字母。
算法1
(排序,双指针) $O((nL \log n) + (n + mL))$
- 首先将所有字符串按字典序排序。
- 维护
s
和t
两个指针,初始时指向 0 和n - 1
。 - 每次读入
searchWord
的一个字符,然后向后移动s
,向前移动t
,直到s > t
或者找到一个符合前缀的字符串。将[s, min(s + 2, t)]
的字符串放进答案中。
时间复杂度
- 排序的时间复杂度为 $O(nL \log n)$,其中 $L$ 为字符串的平均长度。
- 查询时,双指针最坏情况下会经过 $O(n)$ 个位置,每个待搜索的字符需要最坏 $O(L)$ 的时间存放答案,故查询的时间复杂度为 $O(n + mL)$。
空间复杂度
- 只需要 $O(mL)$ 的空间存放答案。
C++ 代码
class Solution {
public:
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
int n = products.size(), m = searchWord.size();
sort(products.begin(), products.end());
vector<vector<string>> ans(m);
int s = 0, t = n - 1;
for (int i = 0; i < m; i++) {
while (s <= t &&
(products[s].size() <= i || products[s][i] != searchWord[i]))
s++;
while (s <= t &&
(products[t].size() <= i || products[t][i] != searchWord[i]))
t--;
for (int j = s; j <= min(s + 2, t); j++)
ans[i].push_back(products[j]);
}
return ans;
}
};
算法2
(Trie 树) $O(L (\sum L + m))$
- 建立一棵字典树,每个结点记录到这个结点为前缀的字典序前 3 小的字符串。
- 建树时,每个结点维护一个大小为 3 的大根堆。
- 查询时,直接将大根堆中的字符串取出即可。
- 这个算法适用于有多个待查询的字符串。
时间复杂度
- 建树时,最坏情况下,Trie 树的每个结点都需要和当前字符串做个比较,故建树的时间复杂度为 $O(L \sum L)$。
- 查询时,$m$ 的每个字符都需要 $O(L)$ 的时间取出答案。
- 故总时间复杂度为 $O(L (\sum L + m))$。
空间复杂度
- Trie 树中的每个结点占用常数的空间,答案需要 $O(mL)$ 的空间,故总空间复杂度为 $O(\sum L)$。
C++ 代码
struct Node {
vector<Node*> nxt;
priority_queue<string> p;
Node() {
nxt.resize(26, NULL);
}
};
class Solution {
public:
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
Node *root = new Node();
for (const auto &s : products) {
Node *cur = root;
for (char c : s) {
if (!cur -> nxt[c - 'a'])
cur -> nxt[c - 'a'] = new Node();
cur = cur -> nxt[c - 'a'];
if ((cur -> p).size() < 3)
(cur -> p).push(s);
else {
if ((cur -> p).top() > s) {
(cur -> p).pop();
(cur -> p).push(s);
}
}
}
}
Node *cur = root;
vector<vector<string>> ans;
for (char c : searchWord) {
if (!cur) {
ans.push_back({});
} else {
cur = cur -> nxt[c - 'a'];
vector<string> tmp;
if (cur != NULL) {
while (!(cur -> p).empty()) {
tmp.push_back((cur -> p).top());
(cur -> p).pop();
}
reverse(tmp.begin(), tmp.end());
}
ans.push_back(tmp);
}
}
return ans;
}
};
后面那个while循环, 里面的 products[t].size() <= i 可以去掉