You are given two gene sequences — a starting gene and a target gene — each represented as an 8-character string made up of 'A', 'C', 'G', and 'T'.
A mutation is defined as a change in exactly one character in the gene string.
For a mutation to be valid, the resulting gene must exist in a provided gene bank.
Your task is to find the minimum number of valid mutations needed to transform the startGene into the endGene.
If it’s not possible to reach the endGene through valid mutations, return -1.
You can assume the startGene is always valid, even if it doesn’t appear in the bank.
Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1
Explanation:
One mutation changes 'T' to 'A' → "AACCGGTA"
Input: startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2
Explanation:
Step 1: "AACCGGTT" → "AACCGGTA" Step 2: "AACCGGTA" → "AAACGGTA"
Accepted:
Submission: