87.Scramble String

https://leetcode.com/problems/scramble-string/

题意不是简单的reverse。

所以每次取分割点，如果l1,r2匹配&&r1,l2匹配，或者l1,l2匹配&&r1,r2匹配。

1.recursive
以下为discuss里的解法，如果不加字母判断的话会tle。
应该可以加一个dp[][][]来记录。

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if(s1==s2)
            return true;

        int len = s1.length();
        int count[26] = {0};
        for(int i=0; i<len; i++)
        {
            count[s1[i]-'a']++;
            count[s2[i]-'a']--;
        }

        for(int i=0; i<26; i++)
        {
            if(count[i]!=0)
                return false;
        }

        for(int i=1; i<=len-1; i++)
        {
            if( isScramble(s1.substr(0,i), s2.substr(0,i)) && isScramble(s1.substr(i), s2.substr(i)))
                return true;
            if( isScramble(s1.substr(0,i), s2.substr(len-i)) && isScramble(s1.substr(i), s2.substr(0,len-i)))
                return true;
        }
        return false;
    }
};    

2.dp
https://leetcode.com/discuss/85424/simple-iterative-dp-java-solution-with-explanation

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1.length() != s2.length()) return false;
        int len = s1.length();
        /**
         * Let F(i, j, k) = whether the substring S1[i..i + k - 1] is a scramble of S2[j..j + k - 1] or not
         * Since each of these substrings is a potential node in the tree, we need to check for all possible cuts.
         * Let q be the length of a cut (hence, q < k), then we are in the following situation:
         * 
         * S1 [   x1    |         x2         ]
         *    i         i + q                i + k - 1
         * 
         * here we have two possibilities:
         *      
         * S2 [   y1    |         y2         ]
         *    j         j + q                j + k - 1
         *    
         * or 
         * 
         * S2 [       y1        |     y2     ]
         *    j                 j + k - q    j + k - 1
         * 
         * which in terms of F means:
         * 
         * F(i, j, k) = for some 1 <= q < k we have:
         *  (F(i, j, q) AND F(i + q, j + q, k - q)) OR (F(i, j + k - q, q) AND F(i + q, j, k - q))
         *  
         * Base case is k = 1, where we simply need to check for S1[i] and S2[j] to be equal 
         * */
        bool F[len][len][len + 1]={};
        for (int k = 1; k <= len; ++k)
            for (int i = 0; i + k <= len; ++i)
                for (int j = 0; j + k <= len; ++j)
                    if (k == 1)
                        F[i][j][k] = s1[i] == s2[j];
                    else for (int q = 1; q < k && !F[i][j][k]; ++q) {
                        F[i][j][k] = (F[i][j][q] && F[i + q][j + q][k - q]) || (F[i][j + k - q][q] && F[i + q][j][k - q]);
                    }
        return F[0][0][len];
    }
};