Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. http://leetcode.com/onlinejudge#question_87

leetcode_scramble_string.cpp

#define MAXN 100

int f[MAXN][MAXN][MAXN];

class Solution {
    public:
        bool dp(int f[MAXN][MAXN][MAXN], const string& s1, const string& s2, int i, int j, int k) {
            if (f[i][j][k] != -1)
                return f[i][j][k] == 1;
            if (k == 1)
                return f[i][j][k] = (s1[i] == s2[j]);
            for (int t = 1; t < k; ++t) {
                if ( ( dp(f, s1, s2, i, j, t) && dp(f, s1, s2, i + t, j + t, k - t) )
                        || ( dp(f, s1, s2, i, j + k - t, t) && dp(f, s1, s2, i + t, j, k - t) ) )
                    return f[i][j][k] = 1;
            }
            return f[i][j][k] = 0;
        }

        bool isScramble(string s1, string s2) {
            if (s1.length() != s2.length())
                return false;
            memset(f, -1, sizeof(f));
            return dp(f, s1, s2, 0, 0, int(s1.length()));
        }
};