## Algorithm

Problem Name: 433. Minimum Genetic Mutation

A gene string can be represented by an 8-character long string, with choices from `'A'`, `'C'`, `'G'`, and `'T'`.

Suppose we need to investigate a mutation from a gene string `startGene` to a gene string `endGene` where one mutation is defined as one single character changed in the gene string.

• For example, `"AACCGGTT" --> "AACCGGTA"` is one mutation.

There is also a gene bank `bank` that records all the valid gene mutations. A gene must be in `bank` to make it a valid gene string.

Given the two gene strings `startGene` and `endGene` and the gene bank `bank`, return the minimum number of mutations needed to mutate from `startGene` to `endGene`. If there is no such a mutation, return `-1`.

Note that the starting point is assumed to be valid, so it might not be included in the bank.

Example 1:

```Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1
```

Example 2:

```Input: startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2
```

Constraints:

• `0 <= bank.length <= 10`
• `startGene.length == endGene.length == bank[i].length == 8`
• `startGene`, `endGene`, and `bank[i]` consist of only the characters `['A', 'C', 'G', 'T']`.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
int step = 1;
deque < string>cur;
dequenext;
cur.push_back(start);
while(!cur.empty()){
string node = cur.front();
cur.pop_front();
for(auto& s: bank){
if(s == "" || !isNeighbor(node, s)) continue;
if(s == end) return step;
next.push_back(s);
s = "";
}
if(cur.empty()){
step++;
swap(cur, next);
}
}
return -1;
}

bool isNeighbor(const string& a, const string& b){
int diff = 0;
for(int i = 0; i < a.size(); i++> if(a[i] != b[i] && ++diff > 1) return false;
return diff == 1;
}
};
``````
Copy The Code &

Input

cmd
startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]

Output

cmd
1

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int minMutation(String start, String end, String[] bank) {
if (start.equals(end)) {
return 0;
}

Set < String> bankSet = new HashSet<>(Arrays.asList(bank));

char[] charSet = {'A', 'C', 'G', 'T'};
int currLevel = 0;
Set < String> visited = new HashSet<>();

while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
String curr = queue.remove();
if (curr.equals(end)) {
return currLevel;
}

char[] currCharArr = curr.toCharArray();
for (int i = 0; i  <  currCharArr.length; i++) {
char old = currCharArr[i];
for (char c : charSet) {
currCharArr[i] = c;
String newGene = String.valueOf(currCharArr);
if (!visited.contains(newGene) && bankSet.contains(newGene)) {
}
}
currCharArr[i] = old;
}
}

currLevel++;
}

return -1;
}
}
``````
Copy The Code &

Input

cmd
startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]

Output

cmd
1

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const minMutation = function(start, end, bank) {
const obj = { res: Number.MAX_VALUE }
dfs(start, end, bank, 0, obj, new Set())
return obj.res === Number.MAX_VALUE ? -1 : obj.res
}

function dfs(s, e, bank, num, obj, visited) {
if(s === e) {
obj.res = Math.min(obj.res, num)
return
}
for(let el of bank) {
let diff = 0
for(let i = 0, len = s.length; i < len; i++) {
if(s[i] !== el[i]> {
diff++
if(diff > 1) break
}
}
if(diff === 1 && !visited.has(el)) {
dfs(el, e, bank, num + 1, obj, visited)
visited.delete(el)
}
}
}
``````
Copy The Code &

Input

cmd
startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]

Output

cmd
2

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) -> int:
bfs = [start]
genes = set(bank)
cnt = 0
while bfs:
arr = []
for g in bfs:
if g == end:
return cnt
for i, c in enumerate(g):
for new in 'AGTC':
if new != c:
s = g[:i] + new + g[i + 1:]
if s in genes:
arr.append(s)
bfs = arr
cnt += 1
return -1
``````
Copy The Code &

Input

cmd
startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]

Output

cmd
2