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