ระบบแนะนำคำค้นหา (Search Suggestions System) ใน C++

สมมติเรามีอาร์เรย์ของสตริง products และสตริง searchWord เราต้องการออกแบบโมดูลที่แนะนำชื่อผลิตภัณฑ์ได้สูงสุด 3 ชื่อจากรายการ products หลังจากพิมพ์แต่ละตัวอักษรของ searchWord ผลิตภัณฑ์ที่แนะนำต้องมี prefix (คำนำหน้า) ตรงกับ searchWord หากมีมากกว่า 3 ชื่อ ให้คืน 3 ชื่อที่น้อยที่สุดตามลำดับ lexicographical (พจนานุกรม)

ตัวอย่าง

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
  ["mobile","moneypot","monitor"],
  ["mobile","moneypot","monitor"],
  ["mouse","mousepad"],
  ["mouse","mousepad"],
  ["mouse","mousepad"]
]

แนวทางแก้ปัญหา

1. สร้าง map m ที่ key เป็น string (prefix) และ value เป็น vector ของ string (สินค้า)
2. เรียงลำดับอาร์เรย์ products (sort)
3. วนลูปทุกสินค้าใน products:
   • สร้าง prefix x ทีละตัวอักษร
   • ถ้าจำนวนสินค้าใน m[x] น้อยกว่า 3 ให้เพิ่มสินค้าลงไป
4. สร้างผลลัพธ์ res และตัวแปร temp สำหรับสร้าง prefix ของ searchWord
5. วนลูปทุกตัวอักษรใน searchWord:
   • เพิ่มตัวอักษรเข้า temp
   • นำ m[temp] เข้า res
6. คืนค่า res

ตัวอย่างโค้ดเต็ม

#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, ],]