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.
分析：动态规划，dp[i][j][k]表示s1[i~i+len]与s2[j~j+len]是否为Scramble String，即S1从i开始len个字符与S2从j开始len个字符是否为Scramble String。对于每一个分割点，分别判断左右两侧是否是Scramble
String，如果有一个满足，则该子串就满足Scramble String，即
dp[i][j][len]
= (dp[i][j][k] && dp[i+k][j+k][len-k]) || (dp[i][j+len-k][k] && dp[i+k][j][len-k])，当len==1时，dp[i][j][1] = s1[i] == s2[j].
class Solution {
public:
bool isScramble(string s1, string s2)
{
int length = s1.size(),i,j,k,len;
if(length != s2.size())return false;
vector< vector< vector<bool> > >dp(length);
for (i = 0;i < length;++i)
{
vector< vector<bool> >tmp1(length);
for (j = 0;j < length;j++)
{
vector<bool> tmp2(length+1,false);
tmp1[j] = tmp2;
}
dp[i] = tmp1;
}
for (len = 1;len <= length;len++)
{
for (i = 0;i + len <= length;++i)
{
for (j = 0;j +len <= length;++j)
{
if (len == 1)dp[i][j][len] = (s1[i] == s2[j]);
else
{
for (k = 1;k < len;k++)
{
if ((dp[i][j][k] && dp[i+k][j+k][len-k]) || (dp[i][j+len-k][k] && dp[i+k][j][len-k]))
{
dp[i][j][len] = true;//表示s1[i~i+len]与s2[j~j+len]是否为Scramble String
break;
}
}
}
}
}
}
return dp[0][0][length];
}
};