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:
rgeat is a scrambled version of great.
Input:
s1 = "abcde", s2 = "caebd"Output:
falseExplanation:
There is no way to recursively split and swap substrings of 'abcde' to produce 'caebd'.
Input:
s1 = "abc", s2 = "bca"Output:
trueExplanation:
Scrambling 'abc' to get 'bca': Split 'abc' into 'a' and 'bc', then split 'bc' into 'b' and 'c' and swap to get 'cb'. Combining 'a' and 'cb' and swapping gives 'cb'+'a' = 'cba'. This matches the target 'bca'.
Constraints
- •
s1.length == s2.length - •
1 ≤ s1.length ≤ 30