C++-এ ন্যূনতম জিনেটিক মিউটেশন (Minimum Genetic Mutation) সমাধান

একটি জিন স্ট্রিং দৈর্ঘ্য ৮ এবং এতে শুধু A, C, G, T অক্ষর থাকে। একটি মিউটেশন মানে স্ট্রিং-এর একটি ক্যারেক্টার পরিবর্তন। একটি জিন "ব্যাংক"-এ থাকলে সেটি বৈধ মনে করা হয়।

দেওয়া start, end এবং bank থেকে start থেকে end-এ যেতে ন্যূনতম কতটি মিউটেশন দরকার তা বের করতে হবে। অসম্ভব হলে -১ রিটার্ন করুন।

উদাহরণ

ইনপুট: start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

আউটপুট: 2

সমাধানের ধাপসমূহ

প্রতিটি জিন স্ট্রিংর জন্য ৮টি প্যাটার্ন তৈরি করুন (প্রতিটি পজিশনে * দিয়ে)۔
এই প্যাটার্নগুলোকে নোড হিসেবে গ্রাফ তৈরি করুন।
BFS ব্যবহার করে start থেকে end পর্যন্ত সবচোটে পাথ বের করুন।

প্রোগ্রাম উদাহরণ

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

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

ইনপুট

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