问题描述：
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
解题思路：
这道题可以用bfs来解答，与word ladder十分相似。
不过这道题有更多的限制：
1.gene从{‘A‘, ‘C‘, ‘G‘, ‘T‘ }中选择。
2.每一个mutation的结果必须在bank中能够找到。
我们用queue来存储当前的gene string，并且用另一个queue来存储变化次数。
这两个queue要保持同步。
在最开始可以首先检查end是否在bank中，不在bank中的话，无论如何我们也到不达终点，可以直接返回-1.
在检查当前字符串是否可以加入队列时需要检查：
1. 是否已经访问过
2. 是否在bank中可以找到
代码:
class Solution {public: ???int minMutation(string start, string end, vector<string>& bank) { ???????vector<char> genes = {‘A‘, ‘T‘, ‘C‘, ‘G‘}; ???????unordered_set<string> s(bank.begin(), bank.end()); ???????????????if(s.count(end) == 0) return -1; ???????????????unordered_set<string> visited; ???????queue<string> q; ???????queue<int> distance_q; ???????q.push(start); ???????distance_q.push(0); ???????????????while(!q.empty()){ ???????????string cur = q.front(); ???????????q.pop(); ???????????int dis = distance_q.front(); ???????????distance_q.pop(); ???????????for(int i = 0 ; i < 8; i++){ ???????????????for(int j = 0; j < 4; j++){ ???????????????????string temp = cur; ???????????????????if(genes[j] == temp[i]) continue; ???????????????????temp[i] = genes[j]; ???????????????????????????????????????if(temp == end) return dis+1; ???????????????????if(visited.count(temp) == 0 && s.count(temp) != 0){ ???????????????????????visited.insert(temp); ???????????????????????q.push(temp); ???????????????????????distance_q.push(dis+1); ???????????????????} ???????????????} ???????????} ???????} ???????return -1; ???}};433. Minimum Genetic Mutation
原文地址：https://www.cnblogs.com/yaoyudadudu/p/9393852.html