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:
bool isScramble(string s1, string s2) {
int l = s1.length(), i, j, k, t;
if( == l)
return true;
vector<vector<vector<bool>>> dp(l, vector<vector<bool>>(l, vector<bool>(l+, )));
//dp[i][j][k] means s1 starts from index i, s2 starts from index j, if the length k substring is the same
for(i = ; i < l; i++)
{
for(j = ; j < l; j++)
{
dp[i][j][] = (s1[i] == s2[j]);
}
}
for(k = ; k <= l; k++)
{
for(i = ; i < l && i+k <= l; i++)
{
for(j = ; j < l && j+k <= l; j++)
{
for(t = ; t < k; t++)
{
dp[i][j][k] = dp[i][j][t] && dp[i+t][j+t][k-t] || dp[i][j+k-t][t] && dp[i+t][j][k-t];
if(dp[i][j][k])
break;
}
}
}
}
return dp[][][l];
}
};