[LeetCode] Scramble String

Problem Statement (link):

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.

Analysis:
The problem nicely defined the scramble string as a node-swapped binary tree. Thus, we want to check any two siblings that if they are swapped.

Consider base cases:
For any string pairs, if they are of different size or consisted of different sets of letters, they are not scramble string. Further:
- If two string are the same, they are scramble string

Consider the recursion. Suppose we have the following two trees:

    node1
   /    \
left1   right1

    node2
   /    \
left2   right2

we will need to check isScramble(left1, left2) && isScramble(right1, right2), or isScramble(left1, right2) && isScramble(right1, left2), make sure the two strings passed in are the same length, as different-length strings are guaranteed to be non-Scramble.

The time complexity of this recursive algorithm is pretty high though in exponential. It gets pass the OJ because the conditions that I check before going to recursions.

In the worst situation, for any recursion f(n), we will check all the combinations twice, i.e., f(n) = 2[f(1) + f(n-1)] +2[f(2) + f(n-2)] … + 2[f(n/2) + f(n/2+1)], thus, f(n+1)=3*f(n), we have f(n)=3^n.

Code:

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int len=s1.size();
        if (s1==s2) return true;
        if (s1.size()!=s2.size()) return false;
        int val1=0, val2=0;
        for (int i=0; i<len; i++) {
            val1+=s1[i]-'a';
            val2+=s2[i]-'a';
        }
        if (val1!=val2) return false;
       
        for (int i=1; i<len; i++) {
            string a1=s1.substr(0,i);
            string b1=s1.substr(i);
            string a2=s2.substr(0,i);
            string b2=s2.substr(i);
            if (isScramble(a1,a2)&&isScramble(b1,b2))
                return true;
            string a3=s2.substr(len-i);
            string b3=s2.substr(0,len-i);
            if (isScramble(a1,a3)&&isScramble(b1,b3))
                return true;
        }
        return false;
    }
};