সমস্যা বিবরণ
দুটি স্ট্রিং X, Y সিমিলার যদি দুটি ক্যারেক্টার সোয়াপ করে একে অন্য বানানো যায় (বা সমান হয়)। স্ট্রিংসের তালিকা A দেওয়া থাকলে (সবই আনাগ্রাম), কতগুলো কানেক্টেড গ্রুপ আছে তা বের করতে হবে।
উদাহরণ
A = ["tars","rats","arts","star"] → আউটপুট = 2 (গ্রুপ: {tars,rats,arts}, {star})
সমাধান পদ্ধতি
- ইউনিয়ন-ফাইন্ড (DSU) ব্যবহার করা হয়।
- ok(s1,s2) ফাংশন দিয়ে সিমিলারিটি চেক করা হয় (ম্যাক্স ২টি পজিশন ভিন্ন হতে পারে)।
- সব জোড়া স্ট্রিং চেক করে সিমিলার হলে ইউনিয়ন করা হয়।
- গ্রুপ সংখ্যা = নোড সংখ্যা - সফল ইউনিয়ন সংখ্যা।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
cout << "]" << endl;
}
class Solution {
vector<int> parent, rank;
int getParent(int x) {
if (parent[x] == -1) return x;
return parent[x] = getParent(parent[x]);
}
bool unionn(int x, int y) {
int parX = getParent(x), parY = getParent(y);
if (parX == parY) return false;
if (rank[parX] >= rank[parY]) {
rank[parX] += rank[parY];
parent[parY] = parX;
} else {
rank[parY] += rank[parX];
parent[parX] = parY;
}
return true;
}
bool ok(string& s1, string& s2) {
int cnt = 0;
for (int i = 0; i < s1.size(); i++)
if (s1[i] != s2[i]) if (++cnt > 2) return false;
return true;
}
public:
int numSimilarGroups(vector<string>& A) {
int n = A.size(), ret = n;
parent = vector<int>(n, -1);
rank = vector<int>(n, 1);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (ok(A[i], A[j]) && unionn(i, j))
ret--;
return ret;
}
};
int main() {
Solution ob;
vector<string> v = {"tars","rats","arts","star"};
cout << ob.numSimilarGroups(v);
return 0;
}ইনপুট ও আউটপুট
ইনপুট: {"tars","rats","arts","star"}
আউটপুট: 2
