描述

给定一个字符串 s1, 将其递归地分割成两个非空子字符串, 然后可以得到一棵二叉树.

下面是 s1 = "great" 可能得到的一棵二叉树:

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

在攀爬字符串的过程中, 我们可以选择其中任意一个非叶节点, 交换该节点的两个子节点.

例如，我们选择了 "gr" 节点, 并将该节点的两个子节点进行交换, 并且将祖先节点对应的子串部分也交换, 最终得到了 "rgeat". 我们认为 "rgeat" 是 "great" 的一个攀爬字符串.

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

类似地, 如果我们继续将其节点 "eat" 和 "at" 的子节点交换, 又可以得到 "great" 的一个攀爬字符串 "rgtae".

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

给定两个相同长度的字符串 s1 和 s2，判断 s2 是否为 s1 的攀爬字符串.
你可以从任何一棵 s1 可以构造出的二叉树开始攀爬, 但是在攀爬得到 s2 的过程中不能重新构造二叉树.

样例

样例 1:

输入: s1 = "great", s2 = "rgeat"
输出: true
解释: 如同上面描述的.
样例 2:

输入: s1 = "a", s2 = "b"
输出: false

思路：

表示以第位为起点长度为k的字符串是否是以第位为起点长度为k的字符串的攀爬字符串，那么的取值可以表示为:

分别代表s1左串匹配s2左串，s1右串匹配s2右串的情况以及s1左串匹配s2右串，s1右串匹配s2左串的情况。具体实现如下所示。

class Solution {
public:
    /**
     * @param s1: A string
     * @param s2: Another string
     * @return: whether s2 is a scrambled string of s1
     */
    bool isScramble(string &s1, string &s2) {
        // write your code here
        int n=s1.size();
        vector<vector<vector<bool>>> dp(n,vector<vector<bool>>(n,vector<bool>(n+1,false)));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                dp[i][j][1]=s1[i]==s2[j]?true:false;
            }
        }
        for(int k=2;k<=n;k++)
        {
            for(int i=0;i<=n-k;i++)
            {
                for(int j=0;j<=n-k;j++)
                {
                    for(int m=1;m<k;m++)
                    {
                        dp[i][j][k]=dp[i][j][k]||(dp[i][j][m]&&dp[i+m][j+m][k-m])||(dp[i][j+k-m][m]&&dp[i+m][j][k-m]);
                    }
                }
            }
        }
        return dp[0][0][n];
    }
};