Scramble string (C++ code)

Leetcode Scramble String, Apr 30 '121887 / 5901
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
 思路： 直接递归做超时了，因此改用DP，恩，其实是个很典型的DP题了。

0. bool isScramble(string s1, string s2) {  
1.   int n = s1.size();  
2.   if(s2.size() != n) return false;  
3.   if(n == 0) return true;  
4.   bool A[n][n][n+1];  
5.   for(int i = 0; i < n; i++){  
6.    for(int j = 0; j < n; j++){  
7.       A[i][j][1] =(s1[i] == s2[j])? true : false;  
8.    }  
9.  }  
10. for(int k = 2; k < n+1; k++){  
11.   for(int i = 0; i <= n - k; i++){  
12.     for(int j = 0; j <= n - k; j++){  
13.       A[i][j][k] = false;  
14.       for(int m = 1; m < k; m++){  
15.        if(A[i][j][m] && A[i+m][j+m][k-m]) A[i][j][k] = true;       
16.        if(A[i][j+k-m][m] && A[i+m][j][k-m]) A[i][j][k] = true;  
17.       }    
18.     }   
19.   }  
20. }  
21.   
22. return A[0][0][n];  
23.   
24. }   

暴力解法：
bool isScramble(string s1, string s2) {
        if(s1.size() != s2.size()) return false;
        if(s1 == s2) return true;
        int n = s1.length();
        if(n == 0) return true;
        if(n == 1) return s1 == s2;

       for(int i = 1; i < n; i++){

         string s1left = s1.substr(0,i), s1right = s1.substr(i, n-i);
         string s2left = s2.substr(0, i), s2right = s2.substr(i, n-i);
         string s2left2 = s2.substr(0, n-i), s2right2 = s2.substr(n-i, i);

        if(isScramble(s1left, s2left) && isScramble(s1right, s2right)) return true;
        if(isScramble(s1left, s2right) && isScramble(s1right, s2left)) return true;
        if(isScramble(s1left, s2left2) && isScramble(s1right, s2right2)) return true;
        if(isScramble(s1left, s2right2) && isScramble(s1right, s2left2)) return true;

        }
        return false;                   
    }