ধরুন আমরা দুটি অ্যারে শব্দ 1, শব্দ 2 এগুলিকে বাক্য হিসাবে বিবেচনা করেছি এবং একই রকম শব্দ জোড়ার একটি তালিকা দিয়েছি, আমাদের পরীক্ষা করতে হবে দুটি বাক্য একই রকম কিনা। সুতরাং যদি ইনপুট হয় word1 =["মহা", "অভিনয়", "দক্ষতা"] এবং word2 =["সূক্ষ্ম", "নাটক", "প্রতিভা"] এই দুটি অনুরূপ, যদি একই শব্দ জোড়া হয় =[["দারুণ", "ভাল"], ["ভালো", "ভালো"], ["অভিনয়","নাটক"], ["দক্ষতা","প্রতিভা"]]।
সাদৃশ্য সম্পর্ক ট্রানজিটিভ। উদাহরণস্বরূপ, যদি "মহান" এবং "ভাল" একই রকম হয়, এবং "সূক্ষ্ম" এবং "ভাল" একই রকম হয়, তাহলে "মহান" এবং "সূক্ষ্ম"ও একই রকম। এবং মিলটিও প্রতিসম। সুতরাং, "মহান" এবং "সূক্ষ্ম" অনুরূপ হওয়া একই "সূক্ষ্ম" এবং "মহান" একই রকম। একটি শব্দ সবসময় নিজের মতন। সবশেষে, বাক্যগুলো একই রকম হতে পারে যদি তাদের একই সংখ্যক শব্দ থাকে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি মানচিত্রের অভিভাবক, আরেকটি মানচিত্র আইডিএক্স
সংজ্ঞায়িত করুন -
একটি ফাংশন সংজ্ঞায়িত করুন getParent(), এটি x,
লাগবে -
যদি x প্যারেন্টে না থাকে, তাহলে −
-
রিটার্ন x
-
-
পিতামাতা[x] :=getParent(অভিভাবক[x])
-
ফেরত অভিভাবক[x]
-
একটি ফাংশন unionn() সংজ্ঞায়িত করুন, এটি a, b,
লাগবে -
parentA :=getParent(idx[a])
-
parentB :=getParent(idx[b])
-
যদি parentA হয় parentB এর মতো, তাহলে −
-
ফেরত
-
-
পিতামাতা[পিতাতা] :=পিতামাতাবি
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
যদি word1 এর আকার শব্দ2 এর আকারের সমান না হয়, তাহলে −
-
ফেরত মিথ্যা
-
-
n :=শব্দের আকার1
-
কাউন্টার :=1
-
আরম্ভ করার জন্য i :=0, যখন i
-
যদি word1[i] idx-এ না থাকে, তাহলে −
-
idx[words1[i]] :=কাউন্টার, তারপর কাউন্টার 1 দ্বারা বাড়ান
-
-
-
আরম্ভ করার জন্য i :=0, যখন i
-
যদি word2[i] idx-এ না থাকে, তাহলে −
-
idx[words2[i]] :=কাউন্টার, তারপর কাউন্টার 1 দ্বারা বাড়ান
-
-
-
আরম্ভ করার জন্য i :=0, যখন i <জোড়ার আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −
-
u :=জোড়া[i,0]
-
v :=জোড়া[i,1]
-
আপনি যদি idx-এ না থাকেন, তাহলে -
-
idx[u] :=কাউন্টার, তারপর কাউন্টার 1 দ্বারা বাড়ান
-
-
যদি v idx-এ না থাকে, তাহলে -
-
idx[v] :=কাউন্টার, তারপর কাউন্টার 1 দ্বারা বাড়ান
-
-
unionn(u, v)
-
-
আরম্ভ করার জন্য i :=0, যখন i
-
u :=word1[i]
-
v :=word2[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
