स्ट्रिंग्स की सूची genes दी गई है जहां प्रत्येक स्ट्रिंग समान लंबाई की है और केवल 'A', 'C', 'G', 'T' वर्णों से बनी है। दो स्ट्रिंग्स एक ही म्यूटेशन समूह में हैं यदि वे केवल एक वर्ण में भिन्न हैं। यह संबंध संक्रामक है। कुल म्यूटेशन समूहों की संख्या ज्ञात करें।
उदाहरण: ["ACGT", "ACGC", "ACTT", "TTTT", "TGTT"] → 2 समूह: [ACGT, ACGC, ACTT] और [TTTT, TGTT]।
समाधान दृष्टिकोण (यूनियन-फाइंड / DSU)
- प्रत्येक स्ट्रिंग को अपना पैरेंट बनाएं।
- प्रत्येक स्ट्रिंग के लिए, प्रत्येक स्थिति पर प्रत्येक संभावित वर्ण (A,C,G,T) डालकर नई स्ट्रिंग बनाएं।
- यदि नई स्ट्रिंग सेट में मौजूद है, तो दोनों को यूनियन करें।
- अंत में अद्वितीय पैरेंट्स की संख्या गिनें।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
map parent;
string getPar(string& a) {
if (parent[a] == a) return a;
return parent[a] = getPar(parent[a]);
}
bool unite(string& a, string& b) {
string parA = getPar(a), parB = getPar(b);
if (parA != parB) {
parent[parA] = parB;
return true;
}
return false;
}
int solve(vector v) {
sort(v.begin(), v.end());
set s(v.begin(), v.end());
int ret = v.size();
for (auto& it : v) parent[it] = it;
for (auto& it : v) {
for (int j = 0; j < it.size(); j++) {
string temp = it;
for (char x : {'A', 'C', 'G', 'T'}) {
if (x != it[j]) {
temp[j] = x;
if (s.count(temp) && unite(temp, it)) ret--;
}
}
}
}
return ret;
}
};
int main() {
vector v = {"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"};
Solution ob;
cout << ob.solve(v);
return 0;
}
इनपुट
{"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"}
आउटपुट
2