Scramble String

Scramble String

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 {//passed small only
public:
    bool isScramble(string s1, string s2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s1.size() == 1) return s1[0] == s2[0];
        if (s1.empty() || s1.compare(s2) == 0) return true;
        int const max_index = s1.length()-1;
        for(int ii = 1; ii <= max_index; ++ii){
            string const s1_left = s1.substr(0, ii);
            string const s1_right = s1.substr(ii, s1.length()-ii);
            string const s2_left1 = s2.substr(0,ii);
            string const s2_right1 = s2.substr(ii, s2.length()-ii);
            string const s2_left2 = s2.substr(s2.length()-ii, ii);
            string const s2_right2 = s2.substr(0, s2.length()-ii);
            if (isScramble(s1_left, s2_left1) && isScramble(s1_right, s2_right1) 
              || isScramble(s1_left, s2_left2) && isScramble(s1_right, s2_right2))
              return true;
        }
        return false;
    }
};

 class Solution {//passed large
    vector<vector<vector<int> > > record;
    string sa,sb;
public:
    bool process(int pos1, int pos2, int length){
        if (length == 1) return sa[pos1] == sb[pos2];
        if (length == 0) return true;
        if (record[pos1][pos2][length] == 1) return true;
        if (record[pos1][pos2][length] == -1) return false;
        for(int ii = 1; ii < length; ++ii){//ii is size_left
            int const size_right = length - ii;
            if (process(pos1, pos2, ii) && process(pos1+ii, pos2+ii, size_right) 
              || process(pos1, pos2+length-ii,ii) && process(pos1+ii, pos2, size_right)){
                record[pos1][pos2][length] = 1;              
                return true;
              }
        }
        record[pos1][pos2][length] = -1;
        return false;
    }

    bool isScramble(string s1, string s2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        sa = s1;
        sb = s2;
        record.clear();
        record.assign(s1.length()+1,vector<vector<int> >(s1.length()+1, vector<int>(s1.length()+1, 0)));

        return process(0,0,s1.length());
  }
};