C++-এ সিনোনিমাস সেনটেন্স জেনারেশন

সমার্থক শব্দের জোড়ার একটি লিস্ট synonyms এবং একটি বাক্য text দেওয়া আছে। আমাদের সব সম্ভাব্য সমার্থক বাক্য তৈরি করতে হবে যেগুলো লেক্সিকোগ্রাফিক্যালি সর্টেড থাকবে।

ইনপুট: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"

আউটপুট: ৬টি বাক্য যেখানে "happy" এর জায়গায় "joy"/"cheerful" এবং "sad" এর জায়গায় "sorrow" বসে।

সমাধানের ধাপগুলো:

• ইউনিয়ন-ফাইন্ড (DSU) দিয়ে সমার্থক গ্রুপ বানাব

• parent, color, groupByColor ম্যাপ রাখব

• find() ও unionNode() ফাংশন লিখব

• বাক্যকে শব্দে ভাগ করব getString() দিয়ে

• DFS দিয়ে সব কোম্বিনেশন জেনারেট করব dfs() ফাংশনে

• ফলাফল সর্ট করে রিটার্ন করব

উদাহরণ

নিচের কোডটি দেখুন −

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

void print_vector(vector<string> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    map<string, string> parent;
    map<string, int> color;
    map<int, set<string>> groupByColor;
    
    string find(string s) {
        if(parent[s] == s) return s;
        parent[s] = find(parent[s]);
        return parent[s];
    }
    
    void unionNode(string a, string b) {
        string x = find(a);
        string y = find(b);
        if(x == y) return;
        parent[x] = y;
    }
    
    vector<string> ans;
    
    vector<string> getString(string t) {
        vector<string> temp;
        int end = 0;
        string curr = "";
        for(; end < t.size(); end++) {
            if(t[end] == ' ') {
                temp.push_back(curr);
                curr = "";
                continue;
            }
            curr += t[end];
        }
        temp.push_back(curr);
        return temp;
    }
    
    void dfs(vector<string>& strings, int idx, string temp = "") {
        if(idx == strings.size()) {
            ans.push_back(temp);
            return;
        }
        string current = strings[idx];
        if(color.find(current) == color.end()) {
            dfs(strings, idx + 1, temp + current + (idx+1 == strings.size()?"":" "));
        } else {
            set<string> x = groupByColor[color[current]];
            for(auto& z : x) {
                dfs(strings, idx + 1, temp + z + (idx+1 == strings.size()?"":" "));
            }
        }
    }
    
    vector<string> generateSentences(vector<vector<string>>& s, string t) {
        int n = s.size();
        for(int i = 0; i < n; i++) {
            string x = s[i][0];
            string y = s[i][1];
            if(parent.find(x) == parent.end()) parent[x] = x;
            if(parent.find(y) == parent.end()) parent[y] = y;
            unionNode(x, y);
        }
        int c = 1;
        for(int i = 0; i < n; i++) {
            string x = s[i][0];
            string z = s[i][1];
            string y = find(x);
            if(color.find(y) == color.end()) {
                color[y] = c;
                c++;
            }
            color[x] = color[y];
            color[z] = color[y];
            if(groupByColor.find(color[x]) == groupByColor.end()) {
                set<string> ss;
                ss.insert(x);
                ss.insert(y);
                groupByColor[color[x]] = ss;
            } else {
                groupByColor[color[x]].insert(x);
                groupByColor[color[x]].insert(z);
            }
        }
        vector<string> strings = getString(t);
        dfs(strings, 0);
        sort(ans.begin(), ans.end());
        return ans;
    }
};

int main() {
    Solution ob;
    vector<vector<string>> v = {{"happy","joy"},{"sad","sorrow"},{"joy","cheerful"}};
    print_vector(ob.generateSentences(v, "I am happy today but was sad yesterday"));
}

ইনপুট

[["happy","joy"],["sad","sorrow"],["joy","cheerful"]] "I am happy today but was sad yesterday"

আউটপুট

[I am cheerful today but was sad yesterday, I am cheerful today but was sorrow yesterday, I am happy today but was sad yesterday, I am happy today but was sorrow yesterday, I am joy today but was sad yesterday, I am joy today but was sorrow yesterday, ]