程序以查找C ++中的基因的总突变组
假设我们有一个称为基因的字符串列表，其中每个元素具有相同的长度，每个元素包含字符“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