LeetCode 87.扰乱字符串

LeetCode 87.扰乱字符串

使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：

1. 如果字符串的长度为 1 ，算法停止
2. 如果字符串的长度 > 1 ，执行下述步骤：
      在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
      随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
      在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。
   给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。

思路：
f[i,j,m,n]表示从S1[i,j]转移到S2[m,n],属性是成功还是失败。由于每次都是相同的长度，所以可以优化到三维，首先枚举长度k。
由于s 可能是 s = x + y 或者 s = y + x ，所以可能是S1的前一半和S2的前一半匹配，且后两半匹配，或者S1的前一半与S2的后一半匹配且S1的后一半与S2的前一半匹配。

代码：

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int n=s1.size();
        vector<vector<vector<bool>>> f(n, vector<vector<bool>>(n, vector<bool>(n + 1)));
		//一定要先枚举长度
        for(int k=1;k<=n;k++){
            for(int i=0;i + k -1 <n;i++){
                for(int j=0;j + k - 1 < n ;j++){
                    if(k == 1){
                        if(s1[i] == s2[j]){
                            f[i][j][k]=true;
                        }
                    }
                    else{
						 //枚举分界点
                        for(int u=1;u<k;u++){
                            if(f[i][j][u] && f[i+u][j+u][k-u] || f[i][j+k-u][u] && f[i+u][j][k-u]){
                                f[i][j][k]=true;
                                break;
                            }
                        }
                    }
                }
            }
        }
        return f[0][0][n];
    }
};