逐步实现前缀匹配：LeetCode 搜索推荐系统题解与详解

问题描述

我们需要设计一个推荐系统，它接受一个产品数组和一个搜索词。每当用户输入一个字母时，系统应该返回与当前输入前缀匹配的最多三个产品。如果匹配的产品超过三个，则按字典序返回最小的三个。

1268. 搜索推荐系统 - 力扣（LeetCode）

问题拆解

在设计这个推荐系统时，我们的任务是实现一个产品推荐功能：在用户输入每个字母时，根据当前的输入词前缀找出符合条件的前三个产品，并按字典序排列。这个问题可以拆解为几个小步骤，分别处理：

对产品进行排序，使它们在字典序排列。
构建搜索前缀：当用户每次输入一个字母时，逐步构成当前的前缀。
查找匹配产品：根据当前前缀，找到符合要求的最多三个产品。
存储并输出结果：将每次匹配的推荐产品存储在结果列表中。

详细解决方案和实现步骤

1. 对产品进行排序

我们使用 sort() 函数对产品数组进行排序。这样，在后续查找时可以确保找到的结果是按字典序排列的。C++ 中的 sort() 函数是基于快排实现的，平均时间复杂度为 (O(N \log N))，可以有效地对产品进行排序。

sort(products.begin(), products.end());

2. 构建搜索前缀

在处理搜索词时，我们希望每次用户输入一个字母后更新当前前缀，并基于这个前缀寻找匹配的产品。例如，如果搜索词是 “mouse”，那么当用户输入第一个字母 “m” 时，前缀是 “m”；当输入第二个字母 “o” 时，前缀更新为 “mo”。

for (char c : searchWord) {
    prefix += c; // 每次添加一个字母到前缀中

每次循环中，我们根据新的 prefix 来进行产品查找。

3. 查找匹配产品

有了前缀后，我们接下来要做的是找出所有以该前缀开头的产品。由于之前已经排序过产品，所以在循环遍历产品时，一旦找到不匹配的产品，可以立即停止循环。我们使用 find(prefix) == 0 来判断一个产品是否以当前前缀开头。

代码解析

判断前缀匹配：product.find(prefix) == 0 表示当前产品 product 的开头是前缀 prefix。
存储前三个产品：在匹配产品的循环中，一旦找到的匹配产品达到 3 个，即 suggestions.size() == 3，就可以跳出循环，以避免不必要的计算。

for (const string& product : products) {
    if (product.find(prefix) == 0) { // 找到前缀匹配的产品
        suggestions.push_back(product); // 加入到推荐列表
        if (suggestions.size() == 3) // 只保留最多3个
            break;
    }
}

4. 存储并输出结果

每次找到符合条件的推荐产品后，我们将其添加到最终的结果列表 result 中：

result.push_back(suggestions);

完整代码实现

下面是完整的 C++ 实现，包括了以上所有步骤：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
    // 对产品列表按字典序排序
    sort(products.begin(), products.end());
    vector<vector<string>> result; // 最终结果存储
    string prefix; // 当前前缀

    // 遍历每个字符，构建前缀并查找匹配的产品
    for (char c : searchWord) {
        prefix += c; // 构建当前前缀
        vector<string> suggestions; // 当前前缀的推荐产品列表

        // 遍历所有产品，找出匹配前缀的产品
        for (const string& product : products) {
            if (product.find(prefix) == 0) { // 如果产品以前缀开头
                suggestions.push_back(product);
                if (suggestions.size() == 3) // 只保留最多三个推荐
                    break;
            }
        }

        // 将当前前缀的推荐列表加入到结果中
        result.push_back(suggestions);
    }

    return result;
}

// 测试示例
int main() {
    vector<string> products = {"mobile", "mouse", "moneypot", "monitor", "mousepad"};
    string searchWord = "mouse";
    vector<vector<string>> results = suggestedProducts(products, searchWord);

    // 输出结果
    for (const auto& res : results) {
        cout << "[ ";
        for (const auto& str : res) {
            cout << str << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}

运行结果示例

假设输入的 products 为 {"mobile", "mouse", "moneypot", "monitor", "mousepad"}，searchWord 为 "mouse"。代码输出如下：

[ mobile moneypot monitor ]
[ mobile moneypot monitor ]
[ mouse mousepad ]
[ mouse mousepad ]
[ mouse mousepad ]

复杂度分析

时间复杂度： $O(N \log N + M \cdot N)$ ，其中 $N$ 是产品的数量， $M$ 是搜索词的长度。
- 排序复杂度为 $\log N)$ 。
- 查找前缀的复杂度为 $\cdot N)$ 。
空间复杂度：O(M * 3)，其中 (M) 是搜索词的长度，最大推荐产品数为 3。