-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathR38 -> Genetic Mutation
39 lines (38 loc) · 1.01 KB
/
R38 -> Genetic Mutation
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
class Solution {
public:
bool changable(string a, string b){
bool temp=0;
for(int i=0;i<8;i++){
if(a[i]!=b[i]){
if(temp){
return 0;
}
temp=1;
}
}
return temp;
}
int minMutation(string start, string end, vector<string>& bank) {
queue<pair<int,string>> check;
check.push(make_pair(0,start));
int len=bank.size();
while(!check.empty()){
pair<int,string> temp=check.front();
string str=temp.second;
if(str==end){
return temp.first;
}
check.pop();
int changelen=0;
for(int i=0;i<len;i++){
if(changable(str,bank[i])){
check.push(make_pair(temp.first+1,bank[i]));
bank.erase(bank.begin()+i);
i--;
len--;
}
}
}
return -1;
}
};