C++で遺伝子の全突然変異グループを見つけるプログラム

各要素の長さが同じで、各要素に文字「A」、「C」、「G」、「T」が含まれている遺伝子と呼ばれる文字列のリストがあるとします。今、いくつかのルールがあります-

• 2つの文字列s1とs2が1つの文字を除いて同じ文字列である場合、s1とs2は同じミューテーショングループに属します。

• 2つの文字列s1とs2がグループにあり、s2とs3がグループにある場合、s1とs3は同じグループにあります。

生成できる突然変異グループの総数を見つける必要があります。

したがって、入力がgenes =["ACGT"、 "ACGC"、 "ACTT"、 "TTTT"、 "TGTT"]のようである場合、2つの変異グループがあるため、出力は2になります。["ACGT"、 "ACGC"、"ACTT"]および["TTTT"、 "TTTG"]

これを解決するには、次の手順に従います-

• 親と呼ばれる1つのマップを定義します

• 関数getPar（）を定義します。これには、

  が必要です。

• parent [a]がaと同じ場合、次のようになります。

  • を返す

• parent [a] =getPar（parent [a]）

• 親を返す[a]

• 関数unite（）を定義します。これには、a、b、

  が必要です。

• parA：=getPar（a）、parB：=getPar（b）

• parAがparBと等しくない場合、次のようになります。

  • parent [parA]：=parB

  • trueを返す

• falseを返す

• 関数ok（）を定義します。これには、a、b、

  が必要です。

• cnt：=0

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

  • cnt：=cnt +（a[i]がb[i]と同じでない場合は1、それ以外の場合は0）

• cntが1の場合はtrueを返し、それ以外の場合はfalseを返します

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

• 配列を並べ替えるv

• vから要素を取得して1つのセットを定義します

• ret：=vのサイズ

• vの要素ごとに、実行します

  • parent [it]：=it

  • vの要素ごとに、実行します

  • 初期化j：=0の場合、j <サイズの場合、更新（jを1増やします）、次のようにします。

    • temp：=it

    • [A、C、G、T]の各文字xについて

      • xがit[j]と等しくない場合、次のようになります。

        • temp [j]：=x

        • tempがsに存在する場合、次のようになります。

          • unite（temp、it）の場合、次のようになります：

    • retを返す

理解を深めるために、次の実装を見てみましょう-

例

#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