hardDynamic Programming 2DPure DSA~45 min
Is One Token a Scramble of Another
A token can be recursively scrambled: split it into two non-empty parts and optionally swap them, then recurse into each part. Decide whether one token is a scramble of another.
Problem
We can scramble a string s by recursively partitioning it into two non-empty substrings and optionally swapping them, applying the same process to each part. Given two strings s1 and s2 of the same length, return true if s2 is a scramble of s1.
Input
Two strings s1 and s2 of equal length in [1, 30], lowercase letters.
Output
A boolean: whether s2 is a scramble of s1.
Constraints
- s1.length == s2.length
- 1 <= s1.length <= 30
- s1 and s2 consist of lowercase English letters.
Examples
Example 1
Input
s1 = "great", s2 = "rgeat"
Output
true
Swap 'gr' and 'eat' subtrees appropriately to reach rgeat.
Example 2
Input
s1 = "abcde", s2 = "caebd"
Output
false
No sequence of recursive swaps yields caebd.