假设我们有一个称为基因的字符串列表，其中每个元素具有相同的长度，每个元素包含字符“ A”，“ C”，“ G”和/或“ T”。现在有一些规则-
当两个字符串s1和s2是除一个字符之外的相同字符串时，则s1和s2在同一突变组中。
当两个字符串s1和s2在一个组中，而s2和s3在一个组中时，则s1和s3在同一组中。
我们必须找到可以产生的突变组的总数。
因此，如果输入像基因= [“ ACGT”，“ ACGC”，“ ACTT”，“ TTTT”，“ TGTT”]，则输出将为2，因为存在两个突变组：[“ ACGT”， “ ACGC”，“ ACTT”]和[“ TTTT”，“ TTTG”]
为了解决这个问题，我们将遵循以下步骤-
定义一张称为父图
定义一个函数getPar()，这将需要一个
如果parent [a]与a相同，则：
返回一个
parent [a] = getPar（parent [a]）
返回父母[a]
定义一个函数unite()，这将需要a，b，
parA：= getPar(a)，parB：= getPar(b)
如果parA不等于parB，则：
parent [parA]：= parB
返回真
返回假
定义一个函数ok()，这将需要a，b，
cnt：= 0
对于初始化i：= 0，当i <a的大小时，更新（将i增加1），请执行以下操作：
cnt：= cnt +（当a [i]与b [i]不同时为1，否则为0）
当cnt为1时返回true，否则返回false
从主要方法中执行以下操作-
对数组v排序
通过取v中的元素来定义一个s
ret：= v的大小
对于v中的每个元素，执行
temp：=它
对于[A，C，G，T]中的每个字符x
返回ret
temp [j]：= x
如果s中存在temp，则：
如果unite(temp,it)，则：
如果x不等于[j]，则：
parent [it]：=它
对于v中的每个元素，执行
对于初始化j：= 0，当j <它的大小时，更新（将j增加1），执行：
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
map <string, string> 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);
string parB = getPar(b);
if(parA != parB){
parent[parA] = parB;
return true;
}
return false;
}
bool ok(string &a, string& b){
int cnt = 0;
for(int i = 0; i < a.size(); i++){
cnt += a[i] != b[i];
}
return cnt == 1;
}
int solve(vector<string> v) {
sort(v.begin(), v.end());
set <string> 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)){
if(unite(temp, it)) ret--;
}
}
}
}
}
return ret;
}
};
main(){
vector<string> v = {"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"};
Solution(ob);
cout << ob.solve(v);
}{"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"}输出结果
2