## Description

Scramble String

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"`:

``````    great
/    \
gr    eat
/ \    /  \
g   r  e   at
/ \
a   t
``````

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"`.

``````    rgeat
/    \
rg    eat
/ \    /  \
r   g  e   at
/ \
a   t
``````

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"`.

``````    rgtae
/    \
rg    tae
/ \    /  \
r   g  ta  e
/ \
t   a
``````

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.

Example 1:

``````Input: s1 = "great", s2 = "rgeat"
Output: true
``````

Example 2:

``````Input: s1 = "abcde", s2 = "caebd"
Output: false
``````

## Solution

You may considering the string is not always split at the middle.

The tree could be like this:

``````     great
/     \
g       reat
/    \
r      eat
...
``````

### Divide And Conquer (Top to Down)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 `````` ``````func isScramble(s1 string, s2 string) bool { if s1 == s2 { return true } length := len(s1) // couting letters var count int for i := 0; i < length; i++ { count[s1[i]-'a']++ count[s2[i]-'a']-- } // Does letters same? for i := 0; i < 26; i++ { if count[i] != 0 { return false } } for k := 1; k < length; k++ { if isScramble(s1[k:], s2[k:]) && isScramble(s1[:k], s2[:k]) { return true } // exchange substrings if isScramble(s1[k:], s2[:length-k]) && isScramble(s1[:k], s2[length-k:]) { return true } } return false }``````

### Dynamic Programming (Bottom to Up)

Definition `dp[l][i][j]`:

• `s1[i]` start from `'i'`
• `s2[j]` start from `'j'`
• `'l'` is the length of substring, the `length` in recursive solution.

Initialization `dp[i][j] = (s1[i] == s2[j] ? true : false)`.

``````dp[l][i][j] =
// isScramble(s1[k:], s2[k:]) && isScramble(s1[:k], s2[:k])
(dp[k][i][j] && dp[l-k][i+k][j+k]) ||

// isScramble(s1[k:], s2[:length-k]) && isScramble(s1[:k], s2[length-k:])
(dp[k][i][j+l-k] && dp[l-k][i+k][j])
``````

`k` means split the `l` to two parts, so `0 <= k <= l`;

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 `````` ``````func isScramble(s1 string, s2 string) bool { if len(s1) != len(s2) { return false } length := len(s1) dp := make([][][]bool, length+1) for i := 0; i <= length; i++ { dp[i] = make([][]bool, length) for j := 0; j < length; j++ { dp[i][j] = make([]bool, length) } } for i := 0; i < length; i++ { for j := 0; j < length; j++ { dp[i][j] = (s1[i] == s2[j]) } } for l := 2; l <= length; l++ { for i := 0; i < length-l+1; i++ { for j := 0; j < length-l+1; j++ { if dp[l][i][j] { continue } for k := 1; k < l && (!dp[l][i][j]); k++ { dp[l][i][j] = (dp[k][i][j] && dp[l-k][i+k][j+k]) || (dp[k][i][j+l-k] && dp[l-k][i+k][j]) } } } } return dp[length] }``````