Dear readers, today we read this tutorial on minimum genetic mutation in C ++.
If you have a gene string. It can be represented by a string whose length is 8, this string is made up of these letters [A, C, G, T]. Now consider that we want to investigate about a mutation, where the forest mutation is actually a single character that has changed into a gene string. As an example, “AACCGTTT” is replaced with “AACCGTTA”, 1 is the mutation.
We also have a given gene “bank”, where all valid gene mutations are present. A gene must be in the bank so that it can create a valid gene string.
Now if you have given 3 things – start, end, bank, our job is to determine what is the minimum number of mutations needed to get from “start” to “end”. If conversion from beginning to end is not possible, return -1.
Example for Minimum Genetic Mutation in C++ ?
#include <bits/stdc++.h> using namespace std; class MinGenMutProg{ 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(){ MinGenMutProg ob; vector<string> v = {"AACCGGTA", "AACCGCTA", "AAACGGTA"}; cout << (ob.minMutation("AACCGGTT", "AAACGGTA", v)); }
Output
2