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

สมมติว่าเรามีสตริงยีน (gene string) ความยาว 8 ประกอบด้วยตัวอักษร [A, C, G, T] การกลายพันธุ์ 1 ครั้งคือเปลี่ยนตัวอักษร 1 ตัว เช่น "AACCGTTT" → "AACCGTTA" เป็น 1 การกลายพันธุ์

มี "bank" ของยีนที่ถูกต้อง ต้องอยู่ใน bank จึงจะเป็นยีนที่ถูกต้อง

ให้ start, end, bank หาจำนวนการกลายพันธุ์น้อยที่สุดจาก start ไป end หากไม่ได้คืน -1

เช่น start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"] เอาต์พุต = 2

วิธีแก้ − ใช้ BFS บนกราฟที่สร้างจาก pattern วิลด์การ์ด (*) แทนตำแหน่งที่เปลี่ยน

ตัวอย่าง

#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