aboutsummaryrefslogtreecommitdiff
path: root/min_genetic_mutation.cpp
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);
}