Medium

Minimum Genetic Mutation

LAB

Return the minimum number of one-character mutations needed to reach endGene using only genes from bank, or -1.

EXAMPLES

Example 1

Input
{
  "startGene": "AACCGGTT",
  "endGene": "AACCGGTA",
  "bank": [
    "AACCGGTA"
  ]
}

Output
1

FUNCTION SHAPE

startGene: stringendGene: stringbank: stringArray→int

SOLUTION NOTE

This is just brute force BFS. We try all mutations from our given state string.

Reveal reference solution +

pythonREFERENCE

def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
    bank_set = set(bank)
    if endGene not in bank_set:
        return -1

    q = deque([(startGene, 0)])
    genes = ['A', 'C', 'G', 'T']

    while q:
        gene, steps = q.popleft()
        if gene == endGene:
            return steps
        for i in range(len(gene)):
            for c in genes:
                if gene[i] == c:
                    continue
                mutated = gene[:i] + c + gene[i+1:]
                if mutated in bank_set:
                    q.append((mutated, steps + 1))
                    bank_set.remove(mutated)  # Mark as visited

    return -1

TimeO(n * L * 4)

SpaceO(n)

Open on LeetCode ↗