C++에서 유전자의 전체 돌연변이 그룹을 찾는 프로그램

<시간/>

각 요소의 길이가 같고 각 요소에 문자 "A", "C", "G" 및/또는 "T"가 포함되어 있는 유전자라는 문자열 목록이 있다고 가정합니다. 이제 몇 가지 규칙이 있습니다 -

두 문자열 s1과 s2가 한 문자를 제외하고 동일한 문자열이면 s1과 s2는 동일한 돌연변이 그룹에 있습니다.
두 개의 문자열 s1과 s2가 그룹에 있고 s2와 s3이 그룹에 있으면 s1과 s3은 같은 그룹에 있습니다.

생성할 수 있는 돌연변이 그룹의 총 수를 찾아야 합니다.

따라서 입력이 ["ACGT", "ACGC", "ACTT", "TTTT", "TGTT"]와 같은 입력인 경우 두 개의 돌연변이 그룹이 있으므로 출력은 2가 됩니다. ["ACGT", "ACGC", "ACTT"] 및 ["TTTT", "TTTG"]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

부모라는 하나의 맵 정의
getPar() 함수를 정의하면,
부모[a]가 다음과 같으면:
- 반환
부모[a] =getPar(부모[a])
부모 반환[a]
unite() 함수를 정의하면, b,
parA :=getPar(a), parB :=getPar(b)
parA가 parB와 같지 않은 경우:
- 부모[parA] :=parB
- true를 반환
거짓을 반환
ok() 함수를 정의하면, b,
cnt :=0
초기화 i :=0의 경우, i
- cnt :=cnt + (a[i]가 b[i]와 같지 않으면 1, 그렇지 않으면 0)
cnt가 1이면 true를 반환하고, 그렇지 않으면 false를 반환
주요 방법에서 다음을 수행하십시오 -
배열 v
정렬
v
에서 요소를 가져와서 하나의 세트를 정의합니다.
ret :=v의 크기
v의 각 요소에 대해 수행
- 부모[그것] :=그것
- v의 각 요소에 대해 수행
- j:=0 초기화의 경우, j <크기일 때 업데이트(j를 1만큼 증가), 수행:
  - 임시 :=그것
  - [A, C, G, T]의 각 문자 x에 대해
    - x가 [j]와 같지 않으면:
      - 온도[j] :=x
      - temp가 s에 있으면:
        
        합치면(temp, it), 다음:
  - 리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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"}