675. Minimum Genetic Mutation

A gene string has 8 characters from {A, C, G, T}. One mutation changes a single character. Given a start gene, an end gene, and a bank of valid genes, return the minimum number of mutations to transform start into end where every intermediate gene is in the bank, or -1 if impossible. The input is JSON {start, end, bank}.

Input: JSON {start, end, bank}.

Output: Integer — the minimum mutations, or -1.

Examples

Input: {"start":"AACCGGTT","end":"AAACGGTA","bank":["AACCGGTA","AACCGCTA","AAACGGTA"]}
Output: 2
Explanation: Two mutations through the bank.

Input: {"start":"AAAAAAAA","end":"AAAAAAAA","bank":["AAAAAAAA"]}
Output: 0
Explanation: Already equal.

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

Constraints

• gene length 8
• 0<=bank<=10

Asked by