C++ এ সমার্থক বাক্য

ধরুন আমাদের কাছে সমতুল্য সমার্থক শব্দের জোড়ার একটি তালিকা এবং একটি বাক্যের পাঠ্য আছে, আমাদেরকে সব সম্ভাব্য সমার্থক বাক্য খুঁজে বের করতে হবে সেগুলি অভিধানিকভাবে সাজানো হয়েছে।

সুতরাং, যদি ইনপুট প্রতিশব্দের মত হয় =[["সুখী","আনন্দ"],["দুঃখ","দুঃখ"],["আনন্দ","প্রফুল্ল"]], এবং পাঠ্য ="আমি আজ খুশি কিন্তু গতকাল দু:খিত ছিল", তারপর আউটপুট হবে ["আমি আজ প্রফুল্ল কিন্তু গতকাল দুঃখিত", "আমি আজ প্রফুল্ল কিন্তু গতকাল দুঃখিত", "আমি আজ খুশি কিন্তু গতকাল দুঃখিত", "আমি আজ খুশি কিন্তু গতকাল দুঃখ ছিল", "আমি আজ আনন্দ কিন্তু গতকাল দুঃখিত", "আমি আজ আনন্দ কিন্তু গতকাল দুঃখ ছিল"]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• মানচিত্র অভিভাবক, রঙ এবং গ্রুপবাই কালার

  সংজ্ঞায়িত করুন

• একটি ফাংশন সংজ্ঞায়িত করুন find(), এটি s,

  লাগবে

• যদি পিতা-মাতা[s] s এর মতো হয়, তাহলে −

  • পিতামাতা[গণ] :=খুঁজুন(পিতামাতা[গণ])

• অভিভাবক[দের]

  ফেরত দিন

• একটি ফাংশন unionNode() সংজ্ঞায়িত করুন, এটি a, b,

  লাগবে

• x :=খুঁজুন(a), y :=খুঁজুন(b)

• যদি x y এর সমান হয়, তাহলে −

  • পিতামাতা [x] :=y

• একটি অ্যারে উত্তর সংজ্ঞায়িত করুন

• একটি ফাংশন সংজ্ঞায়িত করুন getString(), এটি টি,

  লাগবে

• একটি অ্যারের তাপমাত্রা সংজ্ঞায়িত করুন

• শেষ :=0

• curr :=ফাঁকা স্ট্রিং

• শেষের জন্য করুন

  • যদি t[end] খালি স্থানের সমান হয়, তাহলে −

    • টেম্পের শেষে curr ঢোকান

    • curr :=ফাঁকা স্ট্রিং

    • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

  • curr :=curr concatenate t[শেষ]

• টেম্পের শেষে curr ঢোকান

• রিটার্ন টেম্প

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এটি স্ট্রিং, idx, টেম্প ফাঁকা স্ট্রিং দিয়ে শুরু করবে,

• যদি idx স্ট্রিং এর আকারের সমান হয়, তাহলে −

  • উত্তরের শেষে তাপমাত্রা সন্নিবেশ করুন

  • ফেরত

• বর্তমান :=স্ট্রিংস[আইডিএক্স]

• যদি কারেন্ট রঙ না হয়, তাহলে −

  • dfs(স্ট্রিং, আইডিএক্স + 1, টেম্প + কারেন্ট কনক্যাটেনেট (যদি idx + 1 স্ট্রিংগুলির আকারের সমান হয়, তাহলে ফাঁকা স্ট্রিং, অন্যথায় ফাঁকা স্থান)))

• অন্যথায়

  • একটি সেট সংজ্ঞায়িত করুন x =groupByColor[color[বর্তমান]]

  • x-এ প্রতিটি উপাদান z-এর জন্য, −

    করুন

    • dfs(strings, idx + 1, temp + z +) (যদি idx + 1 স্ট্রিংয়ের আকারের সমান হয়, তাহলে ফাঁকা স্ট্রিং, অন্যথায় ফাঁকা স্থান)))

    • (1 দ্বারা z বাড়ান)

• একটি ফাংশন seeGroups()

  সংজ্ঞায়িত করুন

• groupByColor-এ প্রতিটি উপাদানের জন্য, −

  করুন

  • x :=i এর সেকেন্ড হিসাবে সেট করুন

  • একটি সেট সংজ্ঞায়িত করুন

  • x −

    -এ প্রতিটি উপাদান z এর জন্য

    • (i 1 দ্বারা বাড়ান)

• একটি ফাংশন generateSentences() সংজ্ঞায়িত করুন, এটি একটি 2D অ্যারে s, আরেকটি স্ট্রিং টি,

• n :=s

  এর আকার

• আরম্ভ করার জন্য i :=0, যখন i

  • x :=s[i, 0]

  • y :=s[i, 1]

  • যদি x প্যারেন্টে না থাকে, তাহলে −

    • যদি y পিতামাতার মধ্যে না থাকে, তাহলে −

      • unionNode(x, y)

• c :=1

• আরম্ভ করার জন্য i :=0, যখন i

  • x :=s[i, 0]

  • z :=s[i, 1]

  • y :=খুঁজুন(x)

  • যদি y রঙ না হয়, তাহলে −

    • রঙ[y] :=c

    • (c 1 দ্বারা বৃদ্ধি করুন)

  • রঙ[x] :=রঙ[y]

  • রঙ[z] :=রঙ[y]

  • যদি color[x] groupByColor-এ না থাকে, তাহলে −

    • এক সেট সংজ্ঞায়িত করুন ss

    • ss-এ x ঢোকান

    • ss এ y ঢোকান

    • groupByColor[color[x]] :=ss

  • অন্যথায়

    • groupByColor[color[x]]

      -এ x ঢোকান

    • groupByColor[color[x]]

      -এ z ঢোকান

• একটি অ্যারে স্ট্রিং সংজ্ঞায়িত করুন =getString(t)

• dfs(স্ট্রিং, 0)

• অ্যারে উত্তরগুলি সাজান

• উত্তর ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto< 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]];
         set <string< :: iterator z = x.begin();
         while(z != x.end()){
            dfs(strings, idx + 1, temp + *z + (idx+1 == strings.size()?"":" "));
            z++;
         }
      }
   }
   void seeGroups(){
      map <int, set <string< > :: iterator i = groupByColor.begin();
      while(i != groupByColor.end()){
         set <string< x = i->second;
         set <string< :: iterator z = x.begin();
         while(z != x.end()){
            z++;
         }
         cout << endl;
         i++;
      }
   }
   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;
   }
};
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, ]