C ++中的最小遗传突变
假设我们有一个基因串。可以用长度为8的字符串表示。该字符串由这些字母[A，C，G，T]组成。现在考虑我们要研究一个突变，其中一个突变实际上是基因字符串中一个单独的字符改变了。例如，将“AACCGTTT”更改为“AACCGTTA”为1突变。
我们还有一个给定的基因“bank”，其中存在所有有效的基因突变。一个基因必须在库中才能使其成为有效的基因串。
现在，假设我们给出了3件事-开始，结束，存储，我们的任务是确定从“开始”到“结束”突变所需的最小突变数是多少。如果无法进行从头到尾的转换，则返回-1。
因此，如果输入类似于开始=“AACCGGTT”，结束=“AAACGGTA”，bank=[“AACCGGTA”，“AACCGCTA”，“AAACGGTA”]，则输出将为2。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数putStar()，它将花费s，
定义数组ret
对于初始化i：=0，当i≪s的大小时，更新（将i增加1），执行-
temp：=从0到i-1的s的子字符串连接“*”+从索引i+1到结尾的s的子字符串
在ret的末尾插入temp
返回ret
从主要方法中执行以下操作-
定义一个称为图的映射。
对于初始化i：=0，当i<bank的大小时，更新（将i增加1），执行-
在图[out[j]]的末尾插入s
s：=bank[i]
出=putStar（bank[i]）
对于初始化j：=0，当j<out的大小时，更新（将j增加1），执行
定义一个队列q
将开始插入q
定义一组参观
将开始插入访问
对于初始化lvl：=1，当非q为空时，更新（将lvl增加1），执行-
节点：=q的第一个元素
从q删除元素
out=putStar（节点）
对于初始化i：=0，当i<outofsize时，更新（将i增加1），执行-
v：=graph[u，j]
如果vi被访问，则从循环中出来
如果v与end相同，则返回lvl
将v插入已访问
将v插入q
u：=out[i]
对于初始化j：=0，当j<graph[u]的大小时，更新（将j增加1），执行-
sz：=q的大小
当sz为非零值时，请在每次迭代中减少sz，请执行-
返回-1
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector <string> putStar(string s){
vector <string> ret;
for(int i = 0; i < s.size(); i++){
string temp = s.substr(0, i) + "*" + s.substr(i + 1);
ret.push_back(temp);
}
return ret;
}
int minMutation(string start, string end, vector<string>& bank) {
unordered_map < string, vector <string> > graph;
for(int i = 0; i < bank.size(); i++){
string s = bank[i];
vector <string> out = putStar(bank[i]);
for(int j = 0; j < out.size(); j++){
graph[out[j]].push_back(s);
}
}
queue <string> q;
q.push(start);
set <string> visited;
visited.insert(start);
for(int lvl = 1; !q.empty(); lvl++){
int sz = q.size();
while(sz--){
string node = q.front();
q.pop();
vector <string> out = putStar(node);
for(int i = 0; i < out.size(); i++){
string u = out[i];
for(int j = 0; j < graph[u].size(); j++){
string v = graph[u][j];
if(visited.count(v)) continue;
if(v == end) return lvl;
visited.insert(v);
q.push(v);
}
}
}
}
return -1;
}
};
main(){
Solution ob;
vector<string> v = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
cout << (ob.minMutation("AACCGGTT", "AAACGGTA", v));
}输入项
"AACCGGTT", "AAACGGTA", {"AACCGGTA", "AACCGCTA", "AAACGGTA"}输出结果
2