[LeetCode]Scramble String

class Solution {  
//O(n^4) DP with some cut off can pass the large judge  
//O(n^2) recursion with some cut off can also pass the large judge   
public:  
    bool isScramble(string s1, string s2) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        if(s1.size() != s2.size()) return false;  
        int n = s1.size();  
        if(n == 0) return true;  
        vector<vector<vector<bool> > > f(n, vector<vector<bool> >(n, vector<bool>(n+1, false)));  
        //initialize  
        for(int i = 0; i < n; ++i)  
        {  
            for(int j = 0; j < n; ++j)  
            {  
                if(s1[i] == s2[j]) f[i][j][1] = true;  
            }  
        }  
        //dp  
        for(int len = 2; len <= n; ++len)  
        {  
            for(int i = 0; i < n; ++i)  
            {  
                if(i+len-1 >= n) break;  
                for(int j = 0; j < n; ++j)  
                {  
                    if(j+len-1 >= n) break;  
                    for(int k = 1; k < len; ++k)  
                    {  
                        if(i+k < n && j+k < n) f[i][j][len] = f[i][j][len] || (f[i][j][k] && f[i+k][j+k][len-k]);  
                        if(j+len-k < n && i+k < n) f[i][j][len] = f[i][j][len] || (f[i][j+len-k][k] && f[i+k][j][len-k]);  
                        if(f[i][j][len] == true) break;  
                    }  
                }  
            }  
        }  
        return f[0][0][n];  
    }  
};  

补充：软件开发 , C++ ,

上一个：1062 昂贵的聘礼 （spfa + 等级枚举） - from lanshui_Yang
下一个：poj 2228 Naptime dp