#11Alien DNA Transformation
Given two DNA sequences dna1 and dna2 of the same length, determine whether dna2 can be obtained by recursively rearranging dna1. The sequence can be divided into two non-empty parts at any position, and the two parts can either remain in their original order or be swapped. This process can be applied recursively to the resulting parts. Return true if dna2 can be formed from dna1 through these rearrangements; otherwise, return false.
Real-World Applications: Genetic Sequence Analysis; Data Structure Transformation; Pattern Matching in Bioinformatics;
Examples
Example 1
Input: dna1 = "planet", dna2 = "pnalet"
Output: true
Explanation:
Explanation: One possible transformation is: "planet" → "pl / anet" → "p / l / anet" → "l / p / anet" → "lp / anet" → ... After recursively splitting and optionally swapping parts, "pnalet" can be formed.
Example 2
Input: dna1 = "coding", dna2 = "gcodin"
Output: false
Explanation:
No valid sequence of recursive splits and swaps can transform "coding" into "gcodin".
Example 3
Input: dna1 = "z", dna2 = "z"
Output: true
Explanation:
A single-character sequence is already unchanged.
Constraints
- dna1.length == dna2.length
- 1 <= dna1.length <= 35
- dna1 and dna2 consist only of lowercase English letters.
- Both sequences may contain repeated characters.