#433

Minimum Genetic Mutation

specialist · 775 · lc medium +31 · verified · 56.4% accepted · 3,300 likes · top 51%

Description

A gene sequence is exactly 8 characters built from {'A', 'C', 'G', 'T'}. A single mutation changes exactly one character. Every intermediate gene produced during the transformation must be present in the bank; the starting gene is always valid on its own.

Given startGene, endGene, and bank, return the minimum mutation count to transform startGene into endGene, or -1 if the transformation is impossible.

Example 1:

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

Output: 1

Example 2:

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

Output: 2

Code

1

2

3

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int: