blob: 8bbf50383892339b9e75deb9ffea439538c7a812 (
plain)
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
|
#include "leetcode.h"
class Solution {
public:
int minMutation(string start, string end, vector<string> &bank) {
deque<pair<string, int>> dqp({{start, 0}});
set<string> s(bank.begin(), bank.end());
vector<char> nucleotides = {'A', 'T', 'G', 'C'};
while (!dqp.empty()) {
auto [g, m] = dqp.front();
dqp.pop_front();
if (g == end)
return m;
for (int i = 0; i < g.size(); ++i)
for (char n : nucleotides) {
string gm = g;
gm[i] = n;
if (s.count(gm)) {
s.erase(gm);
dqp.emplace_back(gm, m + 1);
}
}
}
return -1;
}
};
int main() {
Solution obj;
string start = "AACCGGTT", end = "AACCGGTA";
vector<string> bank = {"AACCGGTA"};
cout << obj.minMutation(start, end, bank);
}
|