C++ में न्यूनतम आनुवंशिक उत्परिवर्तन (Minimum Genetic Mutation)

समस्या विवरण

एक जीन स्ट्रिंग 8 अक्षरों की होती है जिसमें केवल [A, C, G, T] अक्षर होते हैं। एक उत्परिवर्तन (mutation) का अर्थ है स्ट्रिंग में एक अक्षर बदलना। उदाहरण: "AACCGTTT" → "AACCGTTA" (1 उत्परिवर्तन)।

एक जीन "बैंक" (bank) दिया गया है जिसमें सभी वैध जीन उत्परिवर्तन हैं। हमें start से end तक पहुंचने के लिए न्यूनतम उत्परिवर्तनों की संख्या ज्ञात करनी है। यदि असंभव है तो -1 लौटाएं।

उदाहरण

इनपुट

start = "AACCGGTT", end = "AAACGGTA"
bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

आउटपुट

2

समाधान दृष्टिकोण (BFS + वाइल्डकार्ड पैटर्न)

1. प्रत्येक जीन के लिए, प्रत्येक स्थिति पर '*' रखकर 8 पैटर्न बनाएं (उदाहरण: "*ACCGGTT", "A*CCGGTT", ...)।
2. एक ग्राफ बनाएं जहां प्रत्येक पैटर्न उन जीनों से जुड़ा है जो उससे मेल खाते हैं।
3. start से BFS शुरू करें। प्रत्येक स्तर एक उत्परिवर्तन दर्शाता है।
4. यदि end मिल जाए, तो स्तर संख्या लौटाएं।
5. यदि कतार खाली हो जाए, तो -1 लौटाएं।

कार्यकारी प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<string> getPatterns(string s) {
        vector<string> ret;
        for (int i = 0; i < s.size(); i++) {
            ret.push_back(s.substr(0, i) + "*" + s.substr(i + 1));
        }
        return ret;
    }
    
    int minMutation(string start, string end, vector<string>& bank) {
        unordered_map<string, vector<string>> graph;
        for (string& gene : bank) {
            for (string& pat : getPatterns(gene)) {
                graph[pat].push_back(gene);
            }
        }
        
        queue<string> q;
        q.push(start);
        unordered_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();
                for (string& pat : getPatterns(node)) {
                    for (string& nei : graph[pat]) {
                        if (visited.count(nei)) continue;
                        if (nei == end) return lvl;
                        visited.insert(nei);
                        q.push(nei);
                    }
                }
            }
        }
        return -1;
    }
};

int main() {
    Solution ob;
    vector<string> bank = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
    cout << ob.minMutation("AACCGGTT", "AAACGGTA", bank);
    return 0;
}

आउटपुट

2