C++ এ ন্যূনতম জেনেটিক মিউটেশন

ধরুন আমাদের একটি জিন স্ট্রিং আছে। এটি একটি স্ট্রিং দ্বারা প্রতিনিধিত্ব করা যেতে পারে যার দৈর্ঘ্য 8, এই স্ট্রিংটি এই অক্ষরগুলি [A, C, G, T] নিয়ে গঠিত। এখন বিবেচনা করুন আমরা একটি মিউটেশন সম্পর্কে তদন্ত করতে চাই, যেখানে একটি মিউটেশন আসলে একটি একক অক্ষর জিন স্ট্রিংয়ে পরিবর্তিত হয়। উদাহরণ হিসেবে, "AACCGTTT" পরিবর্তন করা হয়েছে যেমন "AACCGTTA" হল 1 মিউটেশন।

আমাদের একটি প্রদত্ত জিন "ব্যাঙ্ক" রয়েছে, যেখানে সমস্ত বৈধ জিন মিউটেশন উপস্থিত রয়েছে। একটি জিনকে অবশ্যই একটি বৈধ জিন স্ট্রিং করতে ব্যাঙ্কে থাকতে হবে।

এখন ধরুন আমরা 3টি জিনিস দিয়েছি - শুরু, শেষ, ব্যাঙ্ক, আমাদের কাজ হল "শুরু" থেকে "শেষ" পর্যন্ত মিউটেশন করতে ন্যূনতম কতগুলি মিউটেশন প্রয়োজন তা নির্ধারণ করা। যদি শুরু থেকে শেষ পর্যন্ত রূপান্তর সম্ভব না হয়, তাহলে -1 রিটার্ন করুন।

সুতরাং, যদি ইনপুট হয় start ="AACCGGTT", end ="AAACGGTA", bank =["AACCGGTA", "AACCGCTA", "AAACGGTA"], তাহলে আউটপুট হবে 2।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সংজ্ঞায়িত করুন putStar(), এটি s,

  লাগবে

• একটি অ্যারে ret সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i ≪ s এর আকার, আপডেট করুন (i 1 দ্বারা বাড়ান), করুন −

  • temp :=0 থেকে i-1 পর্যন্ত s-এর সাবস্ট্রিং " * " + সূচী i + 1 থেকে শেষ পর্যন্ত s-এর সাবস্ট্রিং

  • ret-এর শেষে temp সন্নিবেশ করুন

• রিটার্ন রিটার্ন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• গ্রাফ নামে একটি মানচিত্র সংজ্ঞায়িত করুন।

• আরম্ভ করার জন্য i :=0, যখন i <ব্যাঙ্কের আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −

  • s :=ব্যাংক[i]

  • out =putStar(ব্যাংক[i])

  • j শুরু করার জন্য :=0, যখন j <সাইজ অফ আউট, আপডেট (j 1 দ্বারা বাড়ান), করবেন

    • গ্রাফ[out[j]]

      এর শেষে s সন্নিবেশ করুন

• একটি সারি q

  সংজ্ঞায়িত করুন

• q

  -এ স্টার্ট সন্নিবেশ করান

• পরিদর্শন করা একটি সেট সংজ্ঞায়িত করুন

• পরিদর্শন করা

  -এ সূচনা সন্নিবেশ করান

• lvl শুরু করার জন্য :=1, যখন q খালি না থাকে, আপডেট করুন (lvl 1 দ্বারা বাড়ান), করুন −

  • sz :=q এর আকার

  • যখন sz অ-শূন্য, প্রতিটি পুনরাবৃত্তিতে sz হ্রাস করুন, −

    করুন

    • নোড :=q এর প্রথম উপাদান

    • q

      থেকে উপাদান মুছুন

    • out =putStar(নোড)

    • আরম্ভ করার জন্য i :=0, যখন i <সাইজ অফ আউট, আপডেট (i 1 দ্বারা বাড়ান), do−

      • u :=আউট[i]

      • আরম্ভ করার জন্য j :=0, যখন j <গ্রাফের আকার[u], আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), করুন −

        • v :=গ্রাফ[u, j]

        • যদি vi পরিদর্শন করা হয়, তাহলে লুপ থেকে বেরিয়ে আসুন

        • যদি v শেষের মত হয়, তাহলে lvl

          ফেরত দিন

        • ভিজিটেড

          এ সন্নিবেশ করান

        • q

          -এ v সন্নিবেশ করান

• রিটার্ন -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