0% completed
Problem Statement
You have a gene sequence
represented by an 8-character
string, containing only 'A'
, 'C'
, 'G'
, or 'T'
characters. To change from one gene sequence to another, you can mutate one character at a time.
For example, "AAAAACCC" --> "AAAACCCC"
is one mutation.
Each intermediate sequence must be a valid
gene in the provided list (bank).
The gene bank bank
records all the valid gene mutations. A gene must be in bank
to make it a valid gene string.
Given the 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 a mutation, return -1.
Note: The starting point is assumed to be valid, so it might not be included in the bank.
Examples
Example 1:
- Input:
startGene
: "AACCGGTT",endGene
: "AAACGGTA",bank
: ["AACCGGTA", "AACCGCTA", "AAACGGTA"] - Expected Output: 2
- Justification:
- Mutations: "AACCGGTT" → "AACCGGTA" → "AAACGGTA"
Example 2:
- Input:
startGene
: "AAAAACCC",endGene
: "AACCCCCC",bank
: ["AAAACCCC", "AAACCCCC", "AACCCCCC"] - Expected Output: 3
- Justification:
- Mutations: "AAAAACCC" → "AAAACCCC" → "AAACCCCC" → "AACCCCCC"
Example 3:
- Input:
startGene
: "AACCGGTT",endGene
: "CCGGTTAA",bank
: ["AACCGGTA", "AACCGCTA", "AAACGGTA", "CCGGTTAA"] - Expected Output: -1
- Justification: We need to mutate a total of 8 characters, but the 'bank' array contains only 4 strings. So, it is not possible to perform 8 mutations.
Try it yourself
Try solving this question here:
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible