Hệ thống gợi ý tìm kiếm (Search Suggestions System) trong C++

Giả sử chúng ta có mảng chuỗi products và chuỗi searchWord. Chúng ta muốn thiết kế một module gợi ý tối đa ba tên sản phẩm từ danh sách products sau mỗi ký tự của searchWord được gõ. Các sản phẩm gợi ý phải có tiền tố chung với searchWord. Khi có hơn ba sản phẩm cùng tiền tố, trả về ba sản phẩm nhỏ nhất theo thứ tự từ điển. Cần tìm danh sách sản phẩm gợi ý sau mỗi ký tự của searchWord.

Ví dụ: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse", kết quả: [["mobile","moneypot","monitor"], ["mobile","moneypot","monitor"], ["mouse","mousepad"], ["mouse","mousepad"], ["mouse","mousepad"]]

Giải pháp:

• Định nghĩa map m với khóa string và giá trị list string.

• Sắp xếp mảng products.

• Duyệt từng sản phẩm, xây dựng từng tiền tố và lưu tối đa 3 sản phẩm đầu tiên cho mỗi tiền tố.

• Tạo ma trận kết quả res, biến temp lưu tiền tố hiện tại.

• Duyệt từng ký tự của searchWord, cập nhật temp và lấy danh sách gợi ý từ map.

• Trả về res.

Ví dụ hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<string>> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << "[";
        for (int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}
class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& p, string s) {
        map<string, vector<string>> m;
        sort(p.begin(), p.end());
        for (int i = 0; i < p.size(); i++) {
            string x = "";
            for (int j = 0; j < p[i].size(); j++) {
                x += p[i][j];
                if (m[x].size() < 3) m[x].push_back(p[i]);
            }
        }
        vector<vector<string>> res;
        string temp = "";
        for (int i = 0; i < s.size(); i++) {
            temp += s[i];
            res.push_back(m[temp]);
        }
        return res;
    }
};
int main() {
    vector<string> v = {"mobile","mouse","moneypot","monitor","mousepad"};
    Solution ob;
    print_vector(ob.suggestedProducts(v, "mouse"));
}

Input

["mobile","mouse","moneypot","monitor","mousepad"] "mouse"

Output

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