266. Scramble String

We can scramble a string s by recursively partitioning it into two non-empty substrings and optionally swapping them, then scrambling each part. Given two strings s1 and s2 of equal length, return true if s2 is a scrambled version of s1. Input: '"s1", "s2"'.

Input: '"s1", "s2"'.

Output: Boolean — true or false.

Examples

Input: "great", "rgeat"
Output: true
Explanation: Valid scramble via swaps.

Input: "abcde", "caebd"
Output: false
Explanation: Not a valid scramble.

Input: "a", "a"
Output: true
Explanation: Trivial.

Constraints

• 1<=s1.length<=30
• s1.length==s2.length

Asked by