A gene string can be represented by an 8-character long string, with choices from "A"
, "C"
, "G"
, "T"
.
Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutation is defined as ONE single character changed in the gene string.
For example, "AACCGGTT"
-> "AACCGGTA"
is 1 mutation.
Also, there is a given gene "bank", which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.
Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation, return -1.
Note:
- Starting point is assumed to be valid, so it might not be included in the bank.
- If multiple mutations are needed, all mutations during in the sequence must be valid.
- You may assume start and end string is not the same.
Example 1:
start: "AACCGGTT" end: "AACCGGTA" bank: ["AACCGGTA"] return: 1
Example 2:
start: "AACCGGTT" end: "AAACGGTA" bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"] return: 2
Example 3:
start: "AAAAACCC" end: "AACCCCCC" bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"] return: 3
A:
BFS, 每次在每个位置mutation,
class Solution { public: int minMutation(string start, string end, vector<string>& bank) { unordered_set<string> Sbank; for(auto s:bank){ Sbank.insert(s); } vector<string> curLayer{start}; // since this ask for minimum munation, we use bfs vector<char> gene{'A','C','G','T'}; int res = 0; while(not curLayer.empty()){ res++; vector<string> next; for(auto s : curLayer){ for(int i =0;i<start.length();i++){ char curChar = s[i]; for(int j = 0;j<4;j++){// try all variations if(gene[j] == curChar){ continue; } s[i] = gene[j]; if(Sbank.find(s) != Sbank.end()){ // need require that end is in the bank. if(s == end){ return res; } next.push_back(s);// actually save a copy of s Sbank.erase(s); } } s[i] = curChar; } } curLayer = next; } return -1; } };
注意的是:
需要检查end 是否也在bank里
Casino - Dr. Maryland
ReplyDeleteCasino. 삼척 출장샵 Maryland has something to offer for families with Down Syndrome. 충청북도 출장마사지 With over 600 slot machines, table games, and a variety of games, you'll 수원 출장안마 be able Address: 1 Casino 군포 출장샵 Drive, Anne 평택 출장샵 Arundel County, MD