学步园

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.

方法一：

class Solution {

public: vector<string> s1scr[1600]; int indexs[40][40];
bool isScramble(string s1, string s2) {

  int i, j, k, m;

   int ind, len;
    string ss;
    len=s1.length();

    for(i=0;i<=len*len-1;i++)  s1scr[i].clear();

    k=0;

    for(i=0;i<=len-1;i++)
    for(j=1;j<=len;j++)
    {
        indexs[i][j]=k;
        k++;
    }

    (void) grows(s1,s2);

  ind=indexs[0][s1.length()];
  m=s1scr[ind].size();

 // cin>>xx;  
  if(m==1) {  return 1; }
  else { return 0;}

}
void grows(string ss,string s2) {

    int i, j, ind, indl, indr, len;
    int lenl, lenr, leni, start;
    int n1, n2, m1, m2;
    int size; 
    char xx; 
    string slr, s0;
    len=ss.length(); 
    for(leni=1;leni<=len;leni++)
    for(start=0;start<=len-leni;start++)
    {
    ind=indexs[start][leni];
    if(leni==1)  
       {
        s0=ss.substr(start,1);
        if(s2.find(s0)!=string::npos)
        s1scr[ind].push_back(s0); }
    else 
    for(lenl=1;lenl<=leni-1;lenl++)
        {
        lenr=leni-lenl;
        //sl=ss.substr(start,lenl);
        //sr=ss.substr(start+lenl,lenr);
        indl=indexs[start][lenl];
        indr=indexs[start+lenl][lenr];
        m1=s1scr[indl].size();
        m2=s1scr[indr].size();
        //cout<<"start="<<start<<"lenl="<<lenl<<"lenr="<<lenr<<"\n";
        //cout<<"m1="<<m1<<",m2="<<m2<<"\n";
        //cin>>&xx; 
        for(i=0;i<=m1-1;i++)
        for(j=0;j<=m2-1;j++)
        {
          slr=s1scr[indl][i]+s1scr[indr][j];
         if(s2.find(slr)!= string::npos && isexist(s1scr[ind],slr)==0)
          {
         // cout<<"slr="<<slr<<"\n";
         // cin>>&xx; 
          s1scr[ind].push_back(slr);}
          slr=s1scr[indr][j]+s1scr[indl][i];
              //          cout<<"slr2="<<slr<<"\n";
          if(s2.find(slr)!= string::npos && isexist(s1scr[ind],slr)==0)
          {s1scr[ind].push_back(slr);
          //cout<<"slr="<<slr<<"\n";
          //cin>>&xx; 
          }
        }     
    }

}
}

int isexist(vector <string> &ss, string tt) {

  int i, m;
  m=ss.size();
  for(i=0;i<=m-1;i++)
  if(ss[i].compare(tt)==0) return 1;
  return 0;
}
};

方法二：

3 dimensional dynamic programming: f(i,
j, n) = || ((f(i, j, m) && f(i + m, j + m, n - m)) || f(i, j + n - m, m) && f(i + m, j, n - m)) for 1 < m < n where f(i,
j, n) is true iff substring starts at s1[i] and substring starts at s2[j] both with length n are scrambled

boolean isScramble(String s1, String s2) {
    if(s1.equals(s2))
        return true;
    boolean[][][] scrambled = new boolean[s1.length()][s2.length()][s1.length() + 1];
    for(int i = 0; i < s1.length(); i++)
        for(int j = 0; j < s2.length(); j++){
            scrambled[i][j][0] = true; 
            scrambled[i][j][1] = s1.charAt(i) == s2.charAt(j);
        }

    for(int i = s1.length() - 1; i >= 0 ; i--)
        for(int j = s2.length() - 1; j >= 0; j--)
            for(int n = 2; n <= Math.min(s1.length() - i, s2.length() - j); n ++)
                for(int m = 1; m < n; m++){
                    scrambled[i][j][n] |= scrambled[i][j][m] && scrambled[i + m][j + m][n - m] ||
                            scrambled[i][j + n - m][m] && scrambled[i + m][j][n - m];
                    if(scrambled[i][j][n])  break;
                }
    return scrambled[0][0][s1.length()]; 
}