Description
A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'. There is also a gene bank that records all valid gene mutations. A gene must be in the bank to be a valid mutation. Given two gene strings startGene and endGene and the gene bank, return the minimum number of mutations needed to mutate from startGene to endGene. If there is no such mutation, return -1. Note that the starting point is assumed to be valid, so it might not be included in the bank.
Examples
Input:
startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]Output:
1Explanation:
One mutation: AACCGGTT -> AACCGGTA.
Input:
startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]Output:
2Explanation:
AACCGGTT -> AACCGGTA -> AAACGGTA.
Input:
startGene = "AAAAACCC", endGene = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]Output:
3Explanation:
AAAAACCC -> AAAACCCC -> AAACCCCC -> AACCCCCC.
Constraints
- •
0 ≤ bank.length ≤ 10 - •
startGene.length == endGene.length == bank[i].length == 8 - •
startGene, endGene, and bank[i] consist of only 'A', 'C', 'G', 'T'