433. 最小基因变化 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
int minMutation(string startGene, string endGene, vector<string>& bank) {
if(startGene == endGene)return 0;
char key[4] = {'A','C','G','T'};
unordered_set<string> bankset;
unordered_set<string> visited;
queue<string> qu;
for(auto& s : bank){
bankset.emplace(s);
}
qu.push(startGene);
visited.emplace(startGene);
int step = 1;
while(!qu.empty()){
int sz = qu.size();
for(int i = 0; i < sz; i++){
string curstr = qu.front();
qu.pop();
for(int i = 0; i < 8; i++){
for(int j = 0; j < 4; j++){
if(curstr[i] != key[j]){
string tmp = curstr;
tmp[i] = key[j];
if(!visited.count(tmp) && bankset.count(tmp)){
if(tmp == endGene)return step;
qu.push(tmp);
visited.emplace(tmp);
}
}
}
}
}
step++;
}
return -1;
}
};
每一次都要把当前队列排空算是一次步骤