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 <out of size时，更新（将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"}

输出结果

基础教程