LeetCode 87. 扰乱字符串

LeetCode 87. 扰乱字符串

思路：f[i][j][k]表示s1从i开始翻转长度为K的串与s2从j开始长度为K的串是否相同，我们可以吧字符串分成两段来看

有两种可能，1是不翻转那么如果f[i][j][u]和f[i+u][j+u][k-u]都为真，则f[i][j][k]为真。2是翻转，那么如果f[i+u][j][k-u]和f[i][j+k-u][u]都为真，则f[i][j][k]为真。 代码：

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int n=s1.size();
       vector>> f(n,vector>(n,vector(n+1)));

       for(int k=1;k<=n;k++){
           for(int i=0;i+k<=n;i++){
               for(int j=0;j+k<=n;j++){
                   if(k==1){
                       if(s1[i]==s2[j]) f[i][j][k]=true;
                   }else{
                       for(int u=1;u					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/4748946.html