# 87. Scramble String

字符串用二叉树表示，每个结点是上个结点递归定义，把二叉树中任意一个非叶结点的两个children swap所形成的新树所代表的字符串为原来的字符串scramble str。递归把所有可能的partition验证一遍，和解决二叉树一样的分治思路。这题还可以用DP，需要三维状态，过于复杂。

```cpp
/*
 * @lc app=leetcode id=87 lang=cpp
 *
 * [87] Scramble String
 *
 * https://leetcode.com/problems/scramble-string/description/
 *
 * algorithms
 * Hard (32.10%)
 * Likes:    334
 * Dislikes: 539
 * Total Accepted:    95.4K
 * Total Submissions: 296.6K
 * Testcase Example:  '"great"\n"rgeat"'
 *
 * 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
 * 
 */
class Solution {
public:
    bool isScramble(string s1, string s2) {
         const int N = s1.size();
         if (s2.size() != N) return false;
         if (N == 1) {
            if (s1 == s2) return true;
            return false;
         }
         // check whether is a permutation.
         vector<int> freq(26);
         for (const auto c : s1) --freq[c - 'a'];
         for (const auto c : s2) ++freq[c - 'a'];
         for (int i = 0; i < 26; ++i) {
             if (freq[i] != 0) return false;
         }
         // divide and conquer 
         for (int i = 1; i < N; ++i) {
             const string s1l = s1.substr(0, i);
             const string s1r = s1.substr(i);
             if (isScramble(s1l, s2.substr(0, i)) && isScramble(s1r, s2.substr(i)) ||
             isScramble(s1l, s2.substr(N - i)) && isScramble(s1r, s2.substr(0, N - i)))
             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://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/divide-and-concquer/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.