सी ++ में वाक्य समानता II

मान लीजिए हमने दो सरणियाँ दी हैं, शब्द 1, शब्द 2 इन्हें वाक्य के रूप में माना जाता है, और समान शब्द जोड़े की एक सूची, हमें यह जांचना है कि दो वाक्य समान हैं या नहीं। तो यदि इनपुट शब्द 1 =["महान", "अभिनय", "कौशल"] और शब्द 2 =["ठीक", "नाटक", "प्रतिभा"] जैसा है तो ये दोनों समान हैं, यदि समान शब्द जोड़े जैसे हैं =[["महान", "अच्छा"], ["ठीक", "अच्छा"], ["अभिनय", "नाटक"], ["कौशल", "प्रतिभा"]]।

समानता संबंध सकर्मक है। उदाहरण के लिए, यदि "महान" और "अच्छा" समान हैं, और "ठीक" और "अच्छा" समान हैं, तो "महान" और "ठीक" भी समान हैं। और समानता भी सममित है। तो, "महान" और "ठीक" समान होना "ठीक" जैसा ही है और "महान" समान है। एक शब्द हमेशा अपने जैसा ही होता है। अंत में, वाक्य केवल तभी समान हो सकते हैं जब उनके शब्दों की संख्या समान हो।

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

• एक मैप पैरेंट, दूसरा मैप idx परिभाषित करें

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

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

  • वापसी x

• माता-पिता [x]:=माता-पिता प्राप्त करें (माता-पिता [x])

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

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

  लगेगा

• माता-पिता:=माता-पिता प्राप्त करें (आईडीएक्स [ए])

• पेरेंटबी:=getParent(idx[b])

• अगर पेरेंटए पेरेंटबी के समान है, तो -

  • वापसी

• माता-पिता [माता-पिता]:=माता-पिता बी

• मुख्य विधि से निम्न कार्य करें -

• यदि शब्द1 का आकार शब्द2 के आकार के बराबर नहीं है, तो -

  • झूठी वापसी

• n :=शब्दों का आकार1

• काउंटर :=1

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

  • यदि शब्द1[i] idx में नहीं है, तो -

    • idx[words1[i]] :=काउंटर, फिर काउंटर को 1 से बढ़ाएं

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

  • अगर word2[i] idx में नहीं है, तो -

    • idx[words2[i]] :=काउंटर, फिर काउंटर को 1 से बढ़ाएं

• इनिशियलाइज़ i :=0 के लिए, जब i <जोड़ियों का आकार, अपडेट करें (i से 1 बढ़ाएँ), करें -

  • यू:=जोड़े[i,0]

  • v:=जोड़े[i,1]

  • अगर आप idx में नहीं हैं, तो -

    • idx[u] :=काउंटर, फिर काउंटर को 1 से बढ़ाएं

  • अगर v idx में नहीं है, तो -

    • idx[v] :=काउंटर, फिर काउंटर को 1 से बढ़ाएं

  • Unionn(यू, वी)

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

  • आप:=शब्द1[i]

  • वी:=शब्द2[i]

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

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

  • अगर getParent(idx[u]) getParent(idx[v]) के बराबर नहीं है, तो -

    • झूठी वापसी

• सही लौटें

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   unordered_map<int, int> parent;
   unordered_map<string, int> idx;
   int getParent(int x){
      if (!parent.count(x))
         return x;
      return parent[x] = getParent(parent[x]);
   }
   void unionn(string a, string b){
      int parentA = getParent(idx[a]);
      int parentB = getParent(idx[b]);
      if (parentA == parentB)
         return;
      parent[parentA] = parentB;
   }
   bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<vector<string> >& pairs){
      if (words1.size() != words2.size())
         return false;
      int n = words1.size();
      int counter = 1;
      for (int i = 0; i < n; i++) {
         if (!idx.count(words1[i])) {
            idx[words1[i]] = counter++;
         }
      }
      for (int i = 0; i < n; i++) {
         if (!idx.count(words2[i])) {
            idx[words2[i]] = counter++;
         }
      }
      for (int i = 0; i < pairs.size(); i++) {
         string u = pairs[i][0];
         string v = pairs[i][1];
         if (!idx.count(u)) {
            idx[u] = counter++;
         }
         if (!idx.count(v)) {
            idx[v] = counter++;
         }
         unionn(u, v);
      }
      for (int i = 0; i < n; i++) {
         string u = words1[i];
         string v = words2[i];
         if (u == v)
            continue;
         if (getParent(idx[u]) != getParent(idx[v]))
         return false;
      }
      return true;
   }
};
main(){
   Solution ob;
   vector<string> v = { "great", "acting", "skills" }, v1 = { "fine", "drama", "talent" };
   vector<vector<string> > v2 = { { "great", "good" }, { "fine", "good" }, { "drama", "acting" }, { "skills", "talent" } };
   cout << (ob.areSentencesSimilarTwo(v, v1, v2));
}

इनपुट

{"great","acting","skills"}, {"fine","drama","talent"},
{{"great","good"},{"fine","good"},{"drama","acting"},{"skills","talent"}}

आउटपुट

1