LeetCode 87.扰乱字符串

给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。

注意题目描述： 不一定是从中间等分。

动态规划

确定状态：
设两个字符串分别为T 和S，题目求判断一个字符串T是否可以由S经过题意中的变换而成。
因此，首要前提是T和S的长度相等。
按照题意，S会被分解为S=S1+S2，同理，T=T1+T2。若满足S可变换为T则会有以下两种情况：
情况一： S1对应T1，S2对应T2。
情况二： S1对应T2，S2对应T1。

那么只需要判断是否满足二者之一即可，引出了子问题：

• S1是否对应T1，S2是否对应T2
• S1是否对应T2，S2是否对应T1

状态：
f[i][j][k][h]表示S[i...j]是否对应T[k...h]
由于S和T的子串长度相同，可以只记录起始位置，可优化为：f[i][j][k]，k为子串的长度。
例如：
S,T存在这样的一个划分，Si和Tj为S,T的子串，Si从下标i=7开始，Tj从下标j=0开始，长度为5，f[7][0][5]可表示Si(i=7)对应Tj(j=0)。

转移方程：
枚举所有子串情况一与情况二取OR。
f[i][j][k]表示Si是否对应Tj，枚举Si和Tj小于k的子串，若他们的子串存在两种情况之一，Si和Ti即成立。

初始条件和边界：
对于长度为1的子串：若S[i]=T[j]，f[i][j][1]=true，否则为false
计算顺序k从小到大计算
答案为f[0][0][N]

class Solution {
    public boolean isScramble(String s1, String s2) {
        char []s=s1.toCharArray();
        char []t=s2.toCharArray();
        int m=s.length;
        int n=t.length;
        if(m!=n)
            return false;
        if(m==0)
            return true;
        boolean [][][]f=new boolean[m][m][m+1];
        int i,j,k,w;
        for(i=0;i<m;i++)
        {
            for(j=0;j<m;j++)
            {
                f[i][j][1]=s[i]==t[j];
            }
        }
        for(k=2;k<=m;k++)
        {
            for(i=0;i<=m-k;i++)
            {
                for(j=0;j<=m-k;j++)
                {
                    f[i][j][k]=false;
                    for(w=1;w<=k-1;w++)
                    {
                        if(f[i][j][w]&&f[i+w][j+w][k-w]){
                            f[i][j][k]=true;
                                break;
                        }
                    }
                    for(w=1;w<=k-1;w++)
                    {
                        if(f[i][j+k-w][w]&&f[i+w][j][k-w]){
                            f[i][j][k]=true;
                                break;
                        }
                    }
                }
            }
        }
        return f[0][0][m];
    }
}