All problems

Minimum Genetic Mutation

Medium · graph traversal

A gene is a string of exactly 8 characters, each one of "A", "C", "G" or "T".

A mutation changes exactly one character of a gene into a different letter. A lab only accepts results it already knows about, so a mutation is allowed only if the new gene appears in the list bank. The gene you start from does not have to be in the bank.

You start with start_gene and want to turn it into end_gene using as few mutations as possible. Return that smallest number. If it cannot be done, return -1. If the two genes are already the same, no mutation is needed, so return 0.

The genes in bank are all different from each other.

Examples

Example 1

Input: start_gene = "AACCGGTT", end_gene = "AACCGGTA", bank = ["AACCGGTA"]

Output: 1

Changing the last letter from T to A gives the end gene, and that gene is in the bank.

Example 2

Input: start_gene = "AACCGGTT", end_gene = "AAACGGTA", bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

Output: 2

AACCGGTT becomes AACCGGTA, which becomes AAACGGTA. Each step changes one letter and lands in the bank.

Example 3

Input: start_gene = "AAAAAAAA", end_gene = "CCCCCCCC", bank = ["AAAAAAAC", "CCCCCCCC"]

Output: -1

From AAAAAAAA you can reach AAAAAAAC, but nothing in the bank is one letter away from that on the way to CCCCCCCC.

Constraints

• start_gene, end_gene and every gene in bank have length 8.
• Every character is one of "A", "C", "G" or "T".
• 0 <= len(bank) <= 1000
• The genes in bank are all different.