C++での最小の遺伝子変異

遺伝子ストリングがあるとします。これは、長さが8の文字列で表すことができます。この文字列は、これらの文字[A、C、G、T]で構成されます。ここで、突然変異について調査したいとします。ここで、1つの突然変異は、実際には遺伝子文字列で変更された1つの単一文字です。例として、「AACCGTTT」は「AACCGTTA」が1つの突然変異であるように変更されます。

また、すべての有効な遺伝子変異が存在する特定の遺伝子「バンク」もあります。有効な遺伝子文字列にするには、遺伝子がバンクにある必要があります。

ここで、開始、終了、バンクの3つを指定したと仮定します。タスクは、「開始」から「終了」に変更するために必要な変更の最小数を決定することです。最初から最後まで変換できない場合は、-1を返します。

したがって、入力がstart ="AACCGGTT"、end ="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を返す

• メインの方法から、次のようにします-

• グラフと呼ばれる1つのマップを定義します。

• 初期化i：=0の場合、i <バンクのサイズの場合、更新（iを1増やします）、実行-

  • s：=bank [i]

  • out =putStar（bank [i]）

  • 初期化j：=0の場合、j

    • グラフの最後にsを挿入します[out[j]]

• 1つのキューを定義するq

• qに開始を挿入

• 訪問した1セットを定義する

• 訪問先に開始を挿入

• 初期化レベル：=1の場合、qが空でない場合は、更新（レベルを1増やします）、実行-

  • sz：=qのサイズ

  • szがゼロ以外の場合、反復ごとにszを減らし、-

    を実行します。

    • node：=qの最初の要素

    • qから要素を削除

    • out =putStar（node）

    • 初期化i：=0の場合、i

      • u：=out [i]

      • 初期化j：=0の場合、j

        • v：=グラフ[u、j]

        • viが訪問中の場合は、ループから抜け出します

        • vがendと同じ場合は、lvlを返します

        • 訪問済みにvを挿入

        • vをqに挿入

• -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