Scramble String

Problem

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

---

Idea

如果两个string：s1和s2可以满足在某一个位置i,满足以下任意一种情况：
1. s1[0-i]和s2[0-i]相等或者互为scramble, 且s1[i+1, n]和s2[i+1,n]相等或互为scramble
2. s1[0-i]和s2[n-i, n]相等或者互为scramble， 且s1[i+1,n]和s2[0, n-i-1]相等或互为scramble

---

Solution

---