এই সমস্যায় সমান দৈর্ঘ্যের দুটি স্ট্রিং A এবং B দেওয়া আছে। A[i] এবং B[i] একইভাবের (equivalent) ক্যারেক্টার। এই ইকুিভ্যালেন্স রিফ্লেক্সিভ, সিমেট্রিক এবং ট্রানজিটিভ। একটি তৃতীয় স্ট্রিং S দেওয়া আছে, তার লেক্সিকোগ্রাফিক্যালি স্মলেস্ট ইকুিভ্যালেন্ট স্ট্রিং বের করতে হবে।
উদাহরণ
ইনপুট: A = "parker", B = "morris", S = "parser"
আউটপুট: "makkek"
ব্যাখ্যা: গ্রুপগুলো: [m,p], [a,o], [k,r,s], [e,i]। প্রতিটি গ্রুপের সবচেয়ে ছোট ক্যারেক্টার দিয়ে প্রতিস্থাপন করলে "makkek" পাওয়া যায়।
অ্যালগরিদম: ইউনিয়ন-ফাইন্ড (DSU)
- প্যারেন্ট অ্যারে
parent[26]রাখুন, আরম্ভালি -১। getParent(x)— পাথ কমপ্রেশন সহ রুট খুঁজুন।union(a,b)— ছোট ক্যারেক্টারকে রুট বানান।AএবংB-র সব জোড়ায় ইউনিয়ন করুন।S-র প্রতিটি ক্যারেক্টারের রুট খুঁজে ছোট ক্যারেক্টার দিয়ে রিপ্লেস করুন।
C++ প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
class Solution {
vector<int> parent;
int getParent(char x) {
if (parent[x - 'a'] == -1) return x - 'a';
return parent[x - 'a'] = getParent('a' + parent[x - 'a']);
}
void unionn(char a, char b) {
int pA = getParent(a), pB = getParent(b);
if (pA == pB) return;
if (pA < pB) parent[pB] = pA;
else parent[pA] = pB;
}
public:
string smallestEquivalentString(string A, string B, string S) {
parent = vector<int>(26, -1);
for (int i = 0; i < A.size(); i++)
unionn(A[i], B[i]);
string ret = "";
for (char c : S)
ret += char(getParent(c) + 'a');
return ret;
}
};
int main() {
Solution ob;
cout << ob.smallestEquivalentString("parker", "morris", "parser");
return 0;
}
আউটপুট
makkek
