# 87     Scramble String

## 87. [Scramble String](https://leetcode.com/problems/scramble-string/description/)

## 1. Question

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

## 2. Implementation

**(1) Recursion**

思路: 如果s1和s2长度不同，显然return false。然后由于题目的输入string都只含小写字母，所以我们为了判断两个string是否含有一样的character时，我们利用一个size为26的count数字计数，然后再扫一遍count数组，如果count数组的元素不为0，说明存在不同或者数量不一样的character，此时返回false. 注意这步是必要的，否则会超时。

最后就通过递归的方式调用isScramble, 找出scramble的分割点即可

```java
class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) {
            return true;
        }

        if (s1.length() != s2.length()) {
            return false;
        }

        int[] count = new int[26];

        // Check if s1 and s2 has the same characters
        for (int i = 0; i < s1.length(); i++) {
            ++count[s1.charAt(i) - 'a'];
            --count[s2.charAt(i) - 'a'];
        }

        for (int i = 0; i < 26; i++) {
            if (count[i] != 0) {
                return false;
            }
        }

        int n = s1.length();
        // Check if s1 and s2 are scrambled strings using recursion
        for (int i = 1; i < n; i++) {
            if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))
                || (isScramble(s1.substring(0, i), s2.substring(n - i)) && isScramble(s1.substring(i), s2.substring(0, n - i)))) {
                return true;
            }
        }
        return false;
    }
}
```

**(2) DP**

```
```

## 3. Time & Space Complexity

**Recursion:** 时间复杂度O(4 ^ n), 空间复杂度O(n) 递归的深度是O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/dynamic-programming/87-scramble-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.