मान लीजिए हमारे पास दो सरणियाँ words1, words2 हैं जिन्हें वाक्य माना जाता है, और समान शब्द जोड़ों की एक सूची है, हमें जांचना है कि क्या दो वाक्य समान हैं या नहीं। उदाहरण के लिए, यदि words1 = ["great", "acting", "skills"] और words2 = ["fine", "drama", "talent"] हैं, तो ये दोनों समान हैं, यदि समान शब्द जोड़े हैं = [["great", "good"], ["fine", "good"], ["acting","drama"], ["skills","talent"]]।
समानता संबंध संक्रामक है। उदाहरण के लिए, यदि "great" और "good" समान हैं, और "fine" और "good" समान हैं, तो "great" और "fine" भी समान हैं। और समानता सममित भी है। एक शब्द हमेशा स्वयं के समान होता है। अंत में, वाक्य तभी समान हो सकते हैं जब उनमें समान संख्या में शब्द हों।
हल करने की विधि
हम यूनियन-फाइंड (डिसजॉइंट सेट यूनियन) का उपयोग करेंगे:
- parent और idx मैप परिभाषित करें।
getParent()फ़ंक्शन पथ संपीड़न के साथ पैरेंट ढूंढता है।unionn()फ़ंक्शन दो शब्दों को यूनियन करता है।- मुख्य विधि में:
- यदि words1 और words2 का आकार अलग है, तो false लौटाएं।
- सभी शब्दों को इंडेक्स दें।
- प्रत्येक समान जोड़ी के लिए, इंडेक्स दें और यूनियन करें।
- प्रत्येक स्थान के लिए, यदि शब्द समान नहीं हैं और उनके पैरेंट अलग हैं, तो false लौटाएं।
- true लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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
