# LeetCode 433. Minimum Genetic Mutation

## Description

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

Suppose we need to investigate about a mutation (mutation from “start” to “end”), where ONE mutation is defined as ONE single character changed in the gene string.

For example, “AACCGGTT” -> “AACCGGTA” is 1 mutation.

Also, there is a given gene “bank”, which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things – start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from “start” to “end”. If there is no such a mutation, return -1.

Note:

Starting point is assumed to be valid, so it might not be included in the bank.
If multiple mutations are needed, all mutations during in the sequence must be valid.
You may assume start and end string is not the same.

```Example 1:

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

return: 1

Example 2:

start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

return: 2

Example 3:

start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

return: 3
```

## 描述

```示例 1:

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

```

### 思路

• 使用广度优先遍历，初始字符串为第一层，与初始字符串相差一个字符的字符串为下一层的字符串。
• 遍历寻找字符串，直到找到最重的字符串或者队列为空。
```# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2020-01-30 11:43:15

import collections
from typing import List

class Solution:
def _valid_next(self, current: str, next_: str):
# 判断两个长度相等的字符串，对应位置是否只有 1 个字符不同
return sum(1 for c, n in zip(current, next_) if c != n) == 1

def minMutation(self, start: str, end: str, bank: List[str]) -> int:
queue = collections.deque()
queue.append([start, '', 0])

while queue:
# 当前字符串，当前字符串的前一个字符串，steps
current, previous, steps = queue.popleft()
# 当前字符等于目标字符
if current == end:
return steps
# 找到和 current 字符相差一个字符的字符，并且此字符不能和 current 的上一个字符相等
for item in bank:
if item != previous and self._valid_next(current, item):
queue.append([item, current, steps + 1])

return -1
```