Feature #1: Mutate DNA
Understand how to determine if one DNA sequence can be mutated into another using graph-based mappings. Explore how to handle gene substitutions, cycles in mappings, and constraints in mutation using linear graph concepts. This lesson equips you to solve real-world coding challenges involving string transformations.
We'll cover the following...
Description
Every DNA strand contains multiple chromosomes of different types. The type of genes in these chromosomes varies in different DNA samples. We can mutate a single DNA sample of one species into another by replacing the genes in the chromosomes. However, we can only replace the genes from a list of available samples. For simplicity, let’s say that the genes in chromosomes are represented by lowercase English letters, a, b, c,..., etc. The available samples will be the twenty-six letter lexicon for alphabets. In a single replacement, we can replace all occurrences of the same type of genes with any other available sample from our list. Furthermore, gene replacement must be done one by one. For example, garlano could be converted to gorlono if a is replaced with o. Then, if o is replaced with t, it becomes gtrltnt.
We’ll be provided with two chromosome samples from different DNAs in the form of strings. The genes in these chromosome samples can be of the same or different types. Our task will be to determine whether one sample can be mutated to the other under the provided constraints.
For instance, if we replace all occurrences of a with c, all occurrences of b with d, and all occurrences of c with e, we can transform aabcc into ccdee. However, no substitutions can transform aabaa into aadac.
Solution
The ...