C++-এ Search Suggestions System

ধরি আমাদের একটি স্ট্রিং অ্যারে products এবং একটি স্ট্রিং searchWord আছে। আমরা একটি মডিউল ডিজাইন করতে চাই যা searchWord-এর প্রতিটি ক্যারেক্টার টাইপ হওয়ার পর products লিস্ট থেকে সর্বোচ্চ তিনটি প্রোডাক্ট নাম সাজেস্ট করবে। সাজেস্ট করা প্রোডাক্টগুলো searchWord-এর সাথে কমন প্রিফিক্স রাখতে হবে। যখন তিনটির বেশি প্রোডাক্ট কমন প্রিফিক্স দিয়ে থাকে, তবে লেক্সিকোগ্রাফিক্যালি মিনিমাম তিনটি প্রোডাক্ট রিটার্ন করতে হবে। তাই searchWord-এর প্রতিটি ক্যারেক্টার টাইপ হওয়ার পর সাজেস্ট করা প্রোডাক্টের লিস্ট খুঁজে বের করতে হবে।

ইনপুট যদি এইরকম হয়: [ "mobile","mouse","moneypot","monitor","mousepad" ], এবং searchWord হয় "mouse", তবে আউটপুট হবে [["mobile","moneypot","monitor"], ["mobile","moneypot","monitor"], ["mouse","mousepad"], ["mouse","mousepad"], ["mouse","mousepad"]]

এটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:

• একটি ম্যাপ m ডিফাইন করুন স্ট্রিং টাইপ কী এবং স্ট্রিং ভ্যালুর লিস্ট হিসেবে

• প্রোডাক্ট অ্যারে p সোর্ট করুন

• i = 0 থেকে p.size() - 1 পর্যন্ত লুপ চালান

  • x := খালি স্ট্রিং

  • j = 0 থেকে p[i].length() - 1 পর্যন্ত লুপ চালান

    • x := x + p[i][j]

    • যদি m[x] এর সাইজ ৩-এর চেয়ে ছোট হয়, তবে p[i] m[x] লিস্টে ইনসার্ট করুন

• স্ট্রিং ম্যাট্রিক্স res তৈরি করুন, temp := খালি স্ট্রিং

• i = 0 থেকে s.size() - 1 পর্যন্ত লুপ চালান

  • temp := temp + s[i]

  • m[temp] res-এ ইনসার্ট করুন

• res রিটার্ন করুন

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বোঝার জন্য:

উদাহরণ

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<auto> > 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"));
}

ইনপুট

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

আউটপুট

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