Loading problem...
In molecular biology, DNA sequences are represented as strings of exactly 8 characters, where each character is one of four nucleotide bases: 'A' (Adenine), 'C' (Cytosine), 'G' (Guanine), or 'T' (Thymine).
A single-point transformation occurs when exactly one character in a DNA sequence is replaced with a different nucleotide base. For example, transforming "AACCGGTT" to "AACCGGTA" involves changing the last character from 'T' to 'A', which counts as one transformation.
You are given:
startSequence)endSequence)validSequences) representing all known stable DNA configurationsYour task is to determine the minimum number of single-point transformations required to convert the starting sequence into the target sequence. However, there is a critical constraint: every intermediate sequence during the transformation process must exist in the library of valid sequences. This restriction models the biological reality that only certain DNA configurations are stable and observable.
The starting sequence is assumed to be a valid configuration (even if not explicitly listed in the library), but all subsequent transformations must produce sequences that appear in the valid sequences library.
If it is impossible to transform the starting sequence into the target sequence through valid intermediate steps, return -1.
startSequence = "AACCGGTT"
endSequence = "AACCGGTA"
validSequences = ["AACCGGTA"]1A single transformation changes the last character from 'T' to 'A', and the resulting sequence "AACCGGTA" exists in the valid sequences library.
startSequence = "AACCGGTT"
endSequence = "AAACGGTA"
validSequences = ["AACCGGTA", "AACCGCTA", "AAACGGTA"]2One optimal path: "AACCGGTT" → "AACCGGTA" (change position 8: T→A) → "AAACGGTA" (change position 2: C→A). Both intermediate and final sequences exist in the valid library. Total: 2 transformations.
startSequence = "AACCGGTT"
endSequence = "AAACGGTA"
validSequences = ["AACCGGTA", "AACCGCTA"]-1The target sequence "AAACGGTA" does not exist in the valid sequences library, and there's no valid path to reach it. Therefore, transformation is impossible.
Constraints