Reference no: EM13712962
You have to examine the time and space complexity of algorithm.
Question- Some DNA strings can transform to other strings by breaking into contiguous substrings, reversing some of these substrings, and then reconnecting the substrings in the original order.
For example, x =ACTGCATCAT can transform into y=TCAGCCTATA by breaking x into ACT, GC, ATC, AT, reversing the first, third, and fourth substring, and then reconnecting to form y.
The cost of the transformation is the number of breaks, which is three in the example.
Given two DNA strings of length n each, find the transformation of one string into the other with fewest breaks. Your algorithm should return? if there is no way of transforming one string to the other using this procedure.
Examine the time and space complexity of your algorithm.