分析
-
排序产品数组
- 为了能够快速按字典序找到前缀匹配的产品，首先对
products 按字典序排序
-
前缀匹配
- 对
searchWord 的每个前缀：
- 使用一个变量
cur 保存当前前缀（即累加输入的字母）
- 使用一个指针
k 维护当前搜索范围的起点。对于排序后的数组，可以跳过所有小于 cur 的字符串，加速搜索。
- 遍历从
k 开始的最多三个字符串，检查它们是否以 cur 为前缀，若满足条件则加入推荐结果
-
提前结束
- 对于排序后的数组，如果某个字符串不再满足当前前缀条件，后续的字符串也不可能满足，可以提前结束内层循环
时间复杂度
- 排序：
O(mlogm)，其中 m 是 products 的长度
- 前缀匹配：对于
searchWord 的每个字符，我们最多遍历 products 中 3 个字符串，复杂度为 O(n * avgLen)，其中 n 是 searchWord 的长度，avgLen 是产品的平均长度
总复杂度：O(mlogm + n * avgLen
空间复杂度
空间复杂度为 O(n)
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
|
class Solution
{
public:
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord)
{
// 结果数组
std::vector<std::vector<std::string>> res;
// 按字典序排序产品数组
std::sort(products.begin(), products.end());
// 当前前缀和产品数组的起点指针
std::string cur;
int n = products.size(), k = 0;
// 遍历 searchWord 的每个字母
for (char c : searchWord)
{
cur += c; // 更新当前前缀
// 移动指针 k 跳过所有小于当前前缀的字符串
while (k < n && products[k] < cur)
++k;
// 收集符合条件的最多三个产品
std::vector<std::string> tmp;
for (int i = k; i < n && i < k + 3; ++i)
{
// 判断当前字符串是否以 cur 为前缀
if (products[i].substr(0, cur.size()) == cur)
tmp.push_back(products[i]);
else
break; // 剪枝：后续字符串不会匹配，提前退出
}
// 将当前前缀的推荐结果加入结果数组
res.push_back(tmp);
}
return res;
}
};
|
