Đột biến di truyền tối thiểu trong C ++

Giả sử chúng ta có một chuỗi gen. Điều đó có thể được biểu diễn bằng một chuỗi có độ dài là 8, Chuỗi này bao gồm các chữ cái này [A, C, G, T]. Bây giờ hãy xem xét chúng ta muốn điều tra về một đột biến, trong đó MỘT đột biến thực sự là MỘT ký tự đơn lẻ được thay đổi trong chuỗi gen. Ví dụ:"AACCGTTT" được thay đổi giống như "AACCGTTA" là 1 đột biến.

Chúng tôi cũng có một "ngân hàng" gen nhất định, nơi có tất cả các đột biến gen hợp lệ. Một gen phải có trong ngân hàng để làm cho nó trở thành một chuỗi gen hợp lệ.

Bây giờ, giả sử chúng ta đã đưa ra 3 thứ - bắt đầu, kết thúc, ngân hàng, nhiệm vụ của chúng ta là xác định số lượng đột biến tối thiểu cần thiết để đột biến từ "bắt đầu" đến "kết thúc". Nếu không thể chuyển đổi từ đầu đến cuối, hãy trả về -1.

Vì vậy, nếu đầu vào là start ="AACCGGTT", end ="AAACGGTA", bank =["AACCGGTA", "AACCGCTA", "AAACGGTA"], thì đầu ra sẽ là 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm putStar (), điều này sẽ mất s,
Xác định ret mảng
để khởi tạo i:=0, khi kích thước của i là s, hãy cập nhật (tăng i lên 1), thực hiện -
- temp:=chuỗi con của s từ 0 đến i-1 nối "*" + chuỗi con của s từ chỉ mục i + 1 đến cuối
- chèn tạm thời vào cuối ret
trả lại ret
Từ phương thức chính, thực hiện như sau -
Xác định một bản đồ được gọi là đồ thị.
để khởi tạo i:=0, khi i
- s:=bank [i]
- out =putStar (bank [i])
- để khởi tạo j:=0, khi j
  - chèn s vào cuối biểu đồ [out [j]]
Xác định một hàng đợi q
chèn start vào q
Xác định một tập hợp đã truy cập
chèn bắt đầu vào đã truy cập
để khởi tạo lvl:=1, khi không phải q trống, hãy cập nhật (tăng lvl lên 1), thực hiện -
- sz:=kích thước của q
- trong khi sz khác 0, giảm sz trong mỗi lần lặp, thực hiện -
  - node:=phần tử đầu tiên của q
  - xóa phần tử khỏi q
  - out =putStar (nút)
  - để khởi tạo i:=0, khi i
    - u:=out [i]
    - để khởi tạo j:=0, khi j
      - v:=graph [u, j]
      - nếu vi đã được truy cập, sau đó đi ra từ vòng lặp
      - nếu v giống với end, thì trả về lvl
      - chèn v vào đã thăm
      - chèn v vào q
trả về -1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

"AACCGGTT", "AAACGGTA", {"AACCGGTA", "AACCGCTA", "AAACGGTA"}

Đột biến di truyền tối thiểu trong C ++

Ví dụ

Đầu vào

Đầu ra