การกลายพันธุ์ทางพันธุกรรมขั้นต่ำใน C ++

สมมติว่าเรามีสายยีน ที่สามารถแสดงด้วยสตริงที่มีความยาวเท่ากับ 8 สตริงนี้ประกอบด้วยตัวอักษรเหล่านี้ [A, C, G, T] ตอนนี้ ให้พิจารณาว่าเราต้องการตรวจสอบเกี่ยวกับการกลายพันธุ์ โดยที่การกลายพันธุ์ ONE ครั้งนั้นเป็น ONE อักขระเดียวที่เปลี่ยนแปลงในสายยีน ตัวอย่างเช่น "AACCGTTT" มีการเปลี่ยนแปลงเหมือน "AACCGTTA" เป็นการกลายพันธุ์ 1 ครั้ง

นอกจากนี้เรายังมี "ธนาคาร" ของยีนที่กำหนดซึ่งมีการกลายพันธุ์ของยีนที่ถูกต้องทั้งหมด ยีนต้องอยู่ในธนาคารเพื่อให้เป็นสตริงยีนที่ถูกต้อง

สมมติว่าเราได้ให้ 3 สิ่ง - เริ่มต้น สิ้นสุด ธนาคาร งานของเราคือกำหนดจำนวนการกลายพันธุ์ขั้นต่ำที่จำเป็นในการกลายพันธุ์จาก "เริ่มต้น" เป็น "สิ้นสุด" หากไม่สามารถแปลงตั้งแต่ต้นจนจบได้ ให้คืนค่า -1

ดังนั้น หากอินพุตเป็น start ="AACCGGTT", end ="AAACGGTA", bank =["AACCGGTA", "AACCGCTA", "AAACGGTA"] เอาต์พุตจะเป็น 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน putStar() ซึ่งจะใช้เวลา s

• กำหนดอาร์เรย์ ret

• สำหรับการเริ่มต้น i :=0 เมื่อ i ≪ ขนาดของ s ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • temp :=สตริงย่อยของ s จาก 0 ถึง i-1 ต่อ " * " + สตริงย่อยของ s จากดัชนี i + 1 ถึงสิ้นสุด

  • ใส่ temp ที่ท้าย ret

• รีเทิร์น

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• กำหนดหนึ่งแผนที่เรียกว่ากราฟ

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของธนาคาร ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • s :=ธนาคาร[i]

  • ออก =putStar(ธนาคาร[i])

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • แทรก s ที่ท้ายกราฟ[out[j]]

• กำหนดหนึ่งคิว q

• แทรก start ลงใน q

• กำหนดการเยี่ยมชมหนึ่งชุด

• แทรกเริ่มต้นในการเยี่ยมชม

• สำหรับการเริ่มต้น lvl :=1 เมื่อไม่มี q ว่าง ให้อัปเดต (เพิ่ม lvl ขึ้น 1) ทำ -

  • sz :=ขนาดของ q

  • ในขณะที่ sz ไม่ใช่ศูนย์ ให้ลด sz ในการวนซ้ำแต่ละครั้ง ทำ -

    • โหนด :=องค์ประกอบแรกของ q

    • ลบองค์ประกอบออกจาก q

    • ออก =putStar(โหนด)

    • สำหรับการเริ่มต้น i :=0 เมื่อ i

      • u :=ออก[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"}

ผลลัพธ์

2