1095. Genetic Mutation — Minimum Mutations (BFS)

A gene is a string over 'ACGT'. Given a startGene, an endGene, and a bank of valid genes, one mutation changes exactly one character, and every intermediate gene must be in the bank. Return the minimum number of mutations to transform startGene into endGene, or -1 if impossible. The input is JSON {startGene, endGene, bank}.

Input: JSON {startGene, endGene, bank}.

Output: Integer — minimum mutations, or -1.

Examples

Input: {"startGene":"AACCGGTT","endGene":"AAACGGTA","bank":["AACCGGTA","AACCGCTA","AAACGGTA"]}
Output: 2
Explanation: Two valid mutations.

Input: {"startGene":"AACCGGTT","endGene":"AACCGGTA","bank":["AACCGGTA"]}
Output: 1
Explanation: One mutation.

Input: {"startGene":"AAAAAAAA","endGene":"AAAAAAAC","bank":["AAAAAAAT"]}
Output: -1
Explanation: endGene not in bank.

Constraints

• genes fixed length
• 0<=bank<=10

Asked by