# Q86. Scramble String

直达: <https://leetcode.com/problems/scramble-string/description/>

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.

## 分析

将s1分成两个子字符串s11和s12, 则无论怎么变化, s11和s12的所有的字符串都在s2的相同的子树里，或者左子树s21，或者右子树s12。

如果s11与s21并且s12与s22都满足Scramble或者s11与s22并且s12与s21都满足Scramble，则s1与s2满足Scramble。显然，需要通过递归求解。

## C++代码

```cpp
class Solution {
public:
    bool isScramble(string s1, string s2) {
        if(s1 == s2) return true;
        if(s1.size() != s2.size()) return false;
        string str1 = s1; string str2 = s2;
        sort(str1.begin(), str1.end());
        sort(str2.begin(), str2.end());
        if (str1 != str2) return false;
        for(int i = 1; i < str1.size(); i++){
            string s11 = s1.substr(0, i);
            string s12 = s1.substr(i);
            string s21 = s2.substr(0,i);
            string s22 = s2.substr(i);
            if(isScramble(s11, s21) && isScramble(s12, s22)) return true;
            s21 = s2.substr(s1.size()-i);
            s22 = s2.substr(0, s1.size()-i);
            if(isScramble(s11, s21) && isScramble(s12, s22)) return true;
        }
        return false;
    } 
};
```


---

# 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://senliuy.gitbook.io/leetcode/di-san-zhang/q86-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.