Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> C++

C++ में समानार्थी वाक्य

मान लीजिए कि हमारे पास समानार्थक शब्दों के जोड़े की एक सूची है और एक वाक्य पाठ है, हमें सभी संभावित पर्यायवाची वाक्यों को खोजना होगा, जिन्हें वे लेक्सिकोग्राफिक रूप से क्रमबद्ध करते हैं।

इसलिए, यदि इनपुट समानार्थक शब्द की तरह है =[["खुश", "खुशी"], ["उदास", "दुख"], ["खुशी", "हंसमुख"]], और पाठ ="मैं आज खुश हूं लेकिन कल उदास था", तो आउटपुट होगा ["मैं आज खुश हूं लेकिन कल उदास था", "मैं आज खुश हूं लेकिन कल दुख था", "मैं आज खुश हूं लेकिन कल उदास था", "मैं आज खुश हूं लेकिन कल का गम था", "मैं आज खुशी हूं लेकिन कल उदास था", "मैं आज खुशी हूं लेकिन कल दुख था"]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

  • मैप्स पेरेंट, कलर और ग्रुपबायकोलर को परिभाषित करें

  • फ़ंक्शन को परिभाषित करें ढूंढें(), इसमें s,

    . लगेगा

  • यदि माता-पिता [s] s के समान हैं, तो -

    • माता-पिता [एस]:=ढूंढें (माता-पिता [एस])

  • माता-पिता को लौटाएं[s]

  • एक फ़ंक्शन को परिभाषित करें UnionNode(), इसमें a, b,

    लगेगा

  • एक्स:=ढूंढें (ए), वाई:=ढूंढें (बी)

  • यदि x, y के समान है, तो -

    • माता-पिता [x] :=y

  • एक सरणी को परिभाषित करें ans

  • फ़ंक्शन getString() को परिभाषित करें, इसमें t लगेगा,

  • एक सरणी अस्थायी परिभाषित करें

  • अंत:=0

  • वक्र :=रिक्त स्ट्रिंग

  • अंत के लिए

    • यदि t[end] रिक्त स्थान के समान है, तो -

      • अस्थायी के अंत में curr डालें

      • वक्र :=रिक्त स्ट्रिंग

      • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

    • curr :=curr concatenate t[end]

  • अस्थायी के अंत में curr डालें

  • वापसी अस्थायी

  • एक फ़ंक्शन dfs() को परिभाषित करें, यह स्ट्रिंग्स, idx, अस्थायी इसे रिक्त स्ट्रिंग के साथ प्रारंभ करेगा,

  • यदि idx स्ट्रिंग्स के आकार के समान है, तो -

    • उत्तर के अंत में अस्थायी डालें

    • वापसी

  • वर्तमान:=तार [idx]

  • यदि करंट रंग में नहीं है, तो -

    • dfs(strings, idx + 1, temp + current concatenate ((यदि idx + 1 स्ट्रिंग्स के आकार के समान है, तो रिक्त स्ट्रिंग, अन्यथा रिक्त स्थान)))

  • अन्यथा

    • एक सेट को परिभाषित करें x =groupByColor[color[current]]

    • x में प्रत्येक अवयव z के लिए, −

      . करें

      • dfs(strings, idx + 1, temp + z + ((यदि idx + 1 स्ट्रिंग्स के आकार के समान है, तो रिक्त स्ट्रिंग, अन्यथा रिक्त स्थान)))

      • (1 से z बढ़ाएँ)

  • फ़ंक्शन को परिभाषित करें देखेंसमूह ()

  • groupByColor में प्रत्येक तत्व i के लिए, −

    . करें

    • x :=i का दूसरा सेट के रूप में

    • एक सेट परिभाषित करें

    • x में प्रत्येक तत्व z के लिए −

      • (i 1 से बढ़ाएँ)

  • एक फ़ंक्शन को परिभाषित करें GenerateSentences (), यह एक 2D सरणी s, दूसरा स्ट्रिंग t,

    लेगा

  • n :=s का आकार

  • इनिशियलाइज़ i:=0 के लिए, जब i

    • एक्स:=एस [i, 0]

    • वाई:=एस[i, 1]

    • यदि x जनक में नहीं है, तो -

      • यदि y माता-पिता में नहीं है, तो -

        • UnionNode(x, y)

  • सी:=1

  • इनिशियलाइज़ i:=0 के लिए, जब i

    • एक्स:=एस [i, 0]

    • z :=s[i, 1]

    • वाई:=खोजें (एक्स)

    • यदि y रंग में नहीं है, तो -

      • रंग [y] :=c

      • (c से 1 बढ़ाएँ)

    • रंग [x] :=रंग[y]

    • रंग [z]:=रंग [y]

    • अगर color[x] groupByColor में नहीं है, तो -

      • एक सेट ss परिभाषित करें

      • ss में x डालें

      • y को ss में डालें

      • groupByColor[color[x]] :=ss

    • अन्यथा

      • x को groupByColor[color[x]]

        . में डालें

      • z को groupByColor[color[x]]

        . में डालें

  • ऐरे स्ट्रिंग्स को परिभाषित करें =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, ]

  1. सी ++ में एक समेकित प्रकार (एनम) को कैसे परिभाषित करें?

    एक एन्यूमरेटेड प्रकार एक वैकल्पिक प्रकार का नाम और शून्य या अधिक पहचानकर्ताओं का एक सेट घोषित करता है जिसे प्रकार के मान के रूप में उपयोग किया जा सकता है। प्रत्येक एन्यूमरेटर एक स्थिरांक है जिसका प्रकार एन्यूमरेशन है। उदाहरण के लिए, यदि आप एक ऐसा एप्लिकेशन बना रहे हैं जिसमें कुछ चर के लिए निश्चित सं

  1. C++ . में पहचानकर्ता

    C++ पहचानकर्ता एक ऐसा नाम है जिसका उपयोग किसी चर, फ़ंक्शन, वर्ग, मॉड्यूल, या किसी अन्य उपयोगकर्ता-परिभाषित आइटम की पहचान करने के लिए किया जाता है। एक पहचानकर्ता अक्षर A से Z या a से z या अंडरस्कोर (_) से शुरू होता है और उसके बाद शून्य या अधिक अक्षर, अंडरस्कोर और अंक (0 से 9) होते हैं। C++ पहचानकर्त

  1. Linux पर C++ का सबसे अच्छा IDE क्या है?

    केवल टेक्स्ट एडिटर्स पर बड़े प्रोजेक्ट्स को मैनेज करना मुश्किल है। यदि आप ऐसे मामलों में आईडीई का उपयोग करते हैं तो आप अधिक उत्पादक और कम निराश होने की संभावना रखते हैं। विभिन्न प्रकार के आईडीई हैं और आपको अपनी आवश्यकताओं के अनुरूप सही का चयन करना चाहिए। Linux पर C++ के लिए एक भी सर्वश्रेष्ठ IDE नही