C++의 최소 유전 돌연변이

<시간/>

유전자 문자열이 있다고 가정합니다. 이는 길이가 8인 문자열로 나타낼 수 있습니다. 이 문자열은 [A, C, G, T] 문자로 구성됩니다. 이제 하나의 돌연변이가 실제로 유전자 문자열에서 변경된 하나의 단일 문자인 돌연변이에 대해 조사하고 싶다고 생각합니다. 예를 들어 "AACCGTTT"는 "AACCGTTA"가 1 돌연변이인 것처럼 변경됩니다.

우리는 또한 모든 유효한 유전자 돌연변이가 존재하는 주어진 유전자 "뱅크"를 가지고 있습니다. 유효한 유전자 문자열이 되려면 유전자가 은행에 있어야 합니다.

이제 시작, 끝, 은행이라는 3가지 항목을 지정했다고 가정합니다. 우리의 임무는 "시작"에서 "끝"으로 변경하는 데 필요한 최소 돌연변이 수를 결정하는 것입니다. 처음부터 끝까지 변환할 수 없으면 -1을 반환합니다.

따라서 입력이 start ="AACCGGTT", end ="AAACGGTA", bank =["AACCGGTA", "AACCGCTA", "AAACGGTA"]인 경우 출력은 2가 됩니다.

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

putStar() 함수를 정의하면 s가 필요합니다.
ret 배열 정의
for initialize i :=0, i ≪ 크기가 s일 때 업데이트(i 1씩 증가), 수행 -
- temp :=0에서 i-1까지 s의 부분 문자열 연결 " * " + 인덱스 i + 1에서 끝까지 s의 부분 문자열
- ret 끝에 temp 삽입
리턴 렛
주요 방법에서 다음을 수행하십시오 -
그래프라는 하나의 지도를 정의합니다.
초기화 i :=0의 경우, i <뱅크의 크기일 때 업데이트(i를 1만큼 증가), 수행 -
- s :=은행[i]
- 출력 =putStar(bank[i])
- j 초기화의 경우:=0, j
  - 그래프 끝에 s 삽입[out[j]]
하나의 대기열 정의 q
q에 시작 삽입
방문한 한 세트 정의
방문에 시작 삽입
initialize lvl :=1의 경우 q가 비어 있지 않으면 업데이트(lvl을 1씩 증가)하고 -
를 수행합니다.
- sz :=q의 크기
- sz가 0이 아닌 동안 각 반복에서 sz를 감소시키고 -
  - node :=q의 첫 번째 요소
  - q에서 요소 삭제
  - 출력 =putStar(노드)
  - for initialize i :=0, i
    - 유 :=아웃[i]
    - j 초기화의 경우:=0, j <그래프[u]의 크기일 때 업데이트(j를 1만큼 증가), 수행 -
      - 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"}