# C++ two end BFS 0ms solution

• The idea is to do two-end BFS. Use a vector<string> and an unordered_set<string> to store the valid mutation generated from previous ones. To exclude previously used mutations, use a increment to ensure each mutation can be used only once in each end.

-----> s1 ... e1 <-----
/                         \
start  ------> s2 ... e2 <-----  end
\                         /
------> s3 ... e3 <-----

class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
unordered_map<string, int> map;
for (auto x : bank) map[x] = 0;
if (!map.count(end)) return -1; // only start is assumed to be valid. If end not valid, return -1
vector<string> v = {start};
unordered_set<string> s = {end};
int res = 0;
int increment = 1;
while (v.size() && s.size()) {
for (auto x : v) {
if (s.count(x)) return res;
}
unordered_set<string> tmp = getMutations(map, v, increment);
v = vector<string>(s.begin(), s.end());
s.swap(tmp);
res++;
increment *= -1;
}
return -1;
}

unordered_set<string> getMutations(unordered_map<string, int>& bank, vector<string>& v, int increment) {
unordered_set<string> res;
vector<char> c = {'A', 'C', 'G', 'T'};
for (auto x : v) {
for (int i = 0; i < x.size(); i++) {
for (int j = 0; j < c.size(); j++) {
char tmp = x[i];
x[i] = c[j];
if (bank.count(x) && abs(bank[x] + increment) < 2) {
res.insert(x);
bank[x] += increment;
}
x[i] = tmp;
}
}
}
return res;
}
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.