Minimum Genetic Mutation LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minMutation(string start, string end, vector<string> &bank) {
4
    unordered_set<string> st(bank.begin(), bank.end());
5
    if (st.find(end) == st.end()) return -1;
6

7
    queue<string> q;
8
    q.push(start);
9

10
    unordered_set<string> vis;
11
    vis.insert(start);
12

13
    int res = 0;
14
    while (not q.empty()) {
15
      int sz = q.size();
16

17
      while (sz--) {
18
        string currString = q.front();
19
        q.pop();
20
        if (currString == end) return res;
21

22
        for (int i = 0; i < currString.size(); i++) {
23
          string temp = currString;
24
          for (auto g : string("ATGC")) {
25
            temp[i] = g;
26
            if (st.find(temp) != st.end() and (vis.find(temp) == vis.end())) {
27
              q.push(temp);
28
              vis.insert(temp);
29
            }
30
          }
31
        }
32
      }
33
      res++;
34
    }
35

36
    return -1;
37
  }
38
};