solution.md

# 扰乱字符串
<div class="notranslate">使用下面描述的算法可以扰乱字符串 <code>s</code> 得到字符串 <code>t</code> ：
    <ol>
        <li>如果字符串的长度为 1 ，算法停止</li>
        <li>如果字符串的长度 &gt; 1 ，执行下述步骤：
            <ul>
                <li>在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 <code>s</code> ，则可以将其分成两个子字符串 <code>x</code> 和 <code>y</code>
                    ，且满足 <code>s = x + y</code> 。</li>
                <li><strong>随机</strong> 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，<code>s</code> 可能是
                    <code>s = x + y</code> 或者 <code>s = y + x</code> 。
                </li>
                <li>在 <code>x</code> 和 <code>y</code> 这两个子字符串上继续从步骤 1 开始递归执行此算法。</li>
            </ul>
        </li>
    </ol>

    <p>给你两个 <strong>长度相等</strong> 的字符串 <code>s1</code><em>
        </em>和&nbsp;<code>s2</code>，判断&nbsp;<code>s2</code><em>&nbsp;</em>是否是&nbsp;<code>s1</code><em>&nbsp;</em>的扰乱字符串。如果是，返回
        <code>true</code> ；否则，返回 <code>false</code> 。
    </p>

    <p>&nbsp;</p>

    <p><strong>示例 1：</strong></p>

    <pre><strong>输入：</strong>s1 = "great", s2 = "rgeat"
<strong><br />输出：</strong>true
<strong><br />解释：</strong>s1 上可能发生的一种情形是：
"great" --&gt; "gr/eat" // 在一个随机下标处分割得到两个子字符串
"gr/eat" --&gt; "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」
"gr/eat" --&gt; "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
"g/r / e/at" --&gt; "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」
"r/g / e/at" --&gt; "r/g / e/ a/t" // 继续递归执行此算法，将 "at" 分割得到 "a/t"
"r/g / e/ a/t" --&gt; "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」
算法终止，结果字符串和 s2 相同，都是 "rgeat"
这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true
</pre>

    <p><strong>示例 2：</strong></p>

    <pre><strong>输入：</strong>s1 = "abcde", s2 = "caebd"
<strong><br />输出：</strong>false
</pre>

    <p><strong>示例 3：</strong></p>

    <pre><strong>输入：</strong>s1 = "a", s2 = "a"
<strong><br />输出：</strong>true
</pre>

    <p>&nbsp;</p>

    <p><strong>提示：</strong></p>

    <ul>
        <li><code>s1.length == s2.length</code></li>
        <li><code>1 &lt;= s1.length &lt;= 30</code></li>
        <li><code>s1</code> 和 <code>s2</code> 由小写英文字母组成</li>
    </ul>
</div>
<p>以下错误的选项是？</p>
## aop
### before
```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after
```cpp
int main()
{
    Solution sol;
    string s1 = "great";
    string s2 = "rgeat";
    bool res;
    res = sol.isScramble(s1, s2);
    cout << res << endl;
    return 0;
}
```

## 答案
```cpp
class Solution
{
    unordered_map<string, bool> memo;

public:
    bool isScramble(string s1, string s2)
    {
        if (memo.count(s1 + '_' + s2) != 0)
        {
            return memo[s1 + '_' + s2];
        }
        if (s1 == s2)
        {
            memo[s1 + '_' + s2] = true;
            return true;
        }
        else if (s1.size() == 1)
        {
            memo[s1 + '_' + s2] = false;
            return false;
        }
        bool do_it = false;
        bool not_do = false;
        for (int i = 1; i < s1.size(); i++)
        {
            do_it = isScramble(s1.substr(0, i), s2.substr(s1.size() - 1, s1.size()));
            not_do = isScramble(s1.substr(0, i), s2.substr(0, i));

            if (do_it || not_do)
            {
                memo[s1 + '_' + s2] = true;
                return true;
            }
        }
        memo[s1 + '_' + s2] = false;
        return false;
    }
};
```
## 选项

### A
```cpp
class Solution
{
public:
    bool isScramble(string s1, string s2)
    {
        int n1 = s1.length(), n2 = s2.length();
        if (n1 != n2)
            return false;
        vector<vector<vector<bool>>> dp(n1 + 1, vector<vector<bool>>(n1 + 1, vector<bool>(n1 + 1, false)));
        int i, j, k;
        for (i = 1; i <= n1; i++)
        {
            for (j = 1; j <= n1; j++)
            {
                dp[i][j][1] = (s1[i - 1] == s2[j - 1]);
            }
        }
        for (int len = 2; len <= n1; len++)
        {
            for (i = 1; i <= n1 && i + len <= n1 + 1; i++)
            {
                for (j = 1; j <= n1 && j + len <= n1 + 1; j++)
                {
                    for (k = 1; k < len; k++)
                    {
                        if (dp[i][j][k] && dp[i + k][j + k][len - k])
                        {
                            dp[i][j][len] = true;
                            break;
                        }
                        if (dp[i][j + len - k][k] && dp[i + k][j][len - k])
                        {
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }

        return dp[1][1][n1];
    }
};
```

### B
```cpp
class Solution
{
public:
    bool isScramble(string s1, string s2)
    {

        if (s1.size() != s2.size())
            return false;
        if (s1 == s2)
            return true;
        vector<int> hash(26, 0);

        for (int i = 0; i < s1.size(); i++)
            hash.at(s1[i] - 'a')++;

        for (int j = 0; j < s2.size(); j++)
            hash.at(s2[j] - 'a')--;

        for (int k = 0; k < 26; k++)
        {
            if (hash.at(k) != 0)
                return false;
        }

        for (int i = 1; i < s1.size(); i++)
        {
            if (
                (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i, s1.size() - i), s2.substr(i, s1.size() - i))) || (isScramble(s1.substr(0, i), s2.substr(s1.size() - i)) && isScramble(s1.substr(i), s2.substr(0, s1.size() - i))))
                return true;
        }
        return false;
    }
};
```

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