Description
We can scramble a string by splitting it into two non-empty substrings recursively and swapping them. Given two strings s1 and s2, return true if s2 is a scrambled string of s1.
Examples
Input:
s1 = "great", s2 = "rgeat"Output:
trueExplanation:
Split 'great' into 'gr' and 'eat'. Swap 'gr' to get 'rg'. Result: 'rg'+'eat' = 'rgeat'. One swap suffices.
Input:
s1 = "abcde", s2 = "caebd"Output:
falseExplanation:
No valid split sequence transforms 'abcde' to 'caebd'. DP/recursion exhausts all possibilities, none work.
Input:
s1 = "abc", s2 = "bca"Output:
trueExplanation:
Split 'abc' into 'a'+'bc', swap to 'bc'+'a'='bca'. Or: 'ab'+'c', swap 'ab'->'ba', then 'ba'+'c'->'bac'. Valid.
Constraints
- •
s1.length == s2.length - •
1 ≤ s1.length ≤ 30