## Minimum Genetic Mutation

• Time:O(n4^{\ell}), where n = |\texttt{bank}| and \ell = |\texttt{word}|
• Space:O(n)

## C++

class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
unordered_set<string> bankSet{bank.begin(), bank.end()};
if (!bankSet.count(end))
return -1;

int ans = 0;
queue<string> q{{start}};

while (!q.empty()) {
++ans;
for (int sz = q.size(); sz > 0; --sz) {
string word = q.front();
q.pop();
for (int j = 0; j < word.length(); ++j) {
const char cache = word[j];
for (const char c : {'A', 'C', 'G', 'T'}) {
word[j] = c;
if (word == end)
return ans;
if (bankSet.count(word)) {
bankSet.erase(word);
q.push(word);
}
}
word[j] = cache;
}
}
}

return -1;
}
};


## JAVA

class Solution {
public int minMutation(String start, String end, String[] bank) {
Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
if (!bankSet.contains(end))
return -1;

int ans = 0;
Queue<String> q = new ArrayDeque<>(Arrays.asList(start));

while (!q.isEmpty()) {
++ans;
for (int sz = q.size(); sz > 0; --sz) {
StringBuilder sb = new StringBuilder(q.poll());
for (int j = 0; j < sb.length(); ++j) {
final char cache = sb.charAt(j);
for (final char c : new char[] {'A', 'C', 'G', 'T'}) {
sb.setCharAt(j, c);
final String word = sb.toString();
if (word.equals(end))
return ans;
if (bankSet.contains(word)) {
bankSet.remove(word);
q.offer(word);
}
}
sb.setCharAt(j, cache);
}
}
}

return -1;
}
}