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.
题意：判断s2是否是s1的爬行字符串。
思路：如果s1和s2是scramble，那么必然存在一个在s1上的长度len1,将s1分成s11和s12两段同样有，s21和s22，那么要么s11和s21是scramble的并且s12和s22是scramble的；要么s11和s22是scramble的并且s12和s21是scramble的。如： rgeat 和 great 来说，rgeat 可分成 rg 和 eat 两段， great 可分成 gr 和 eat 两段，rg 和 gr 是scrambled的， eat 和 eat 当然是scrambled。参考了Grandyang和Eason Liu的博客。
代码如下：
class Solution {
public:
bool isScramble(string s1, string s2)
{
if(s1.size() !=s2.size()) return false;
if(s1==s2) return true;
string str1=s1,str2=s2;
sort(str1.begin(),str1.end());
sort(str2.begin(),str2.end());
if(str1 !=str2) return false;
for(int i=;i<s1.size();++i)
{
string s11=s1.substr(,i);
string s12=s1.substr(i);
string s21=s2.substr(,i);
string s22=s2.substr(i);
if(isScramble(s11,s21)&&isScramble(s12,s22))
return true;
else
{
s21=s2.substr(s1.size()-i);
s22=s2.substr(,s1.size()-i);
if(isScramble(s11,s21)&&isScramble(s12,s22))
return true;
}
}
return false;
}
};
注：substr()函数的用法：str.substr(start,Length)从某一位置start开始，指定长度为length的子字符串，若，length为0或者为负数返回空串；若，没有指定该参数，则，从指定位置开始直到字符串的最后。
方法二：动态规划，参见Grandyang的博客，维护量res[i][j][n]，其中i是s1的起始字符，j是s2的起始字符，而n是当前的字符串长度，res[i][j][len]表示的是以i和j分别为s1和s2起点的长度为len的字符串是不是互为scramble。看看递推式，也就是怎么根据历史信息来得到res[i][j][len]:当前s1[i...i+len-1]字符串劈一刀分成两部分，然后分两种情况：第一种是左边和s2[j...j+len-1]左边部分是不是scramble，以及右边和s2[j...j+len-1]右边部分是不是scramble；第二种情况是左边和s2[j...j+len-1]右边部分是不是scramble，以及右边和s2[j...j+len-1]左边部分是不是scramble,如果以上两种情况有一种成立，说明s1[i...i+len-1]和s2[j...j+len-1]是scramble的.
代码如下：
class Solution {
public:
bool isScramble(string s1, string s2)
{
if(s1.size() !=s2.size()) return false;
if(s1==s2) return true;
int len=s1.size();
vector<vector<vector<bool>>> dp(len,
vector<vector<bool>>(len,vector<bool>(len+,false)));
for(int i=;i<len;++i)
{
for(int j=;j<len;++j)
{
dp[i][j][]=(s1[i]==s2[j]);
}
}
for(int n=;n<=len;++n)
{
for(int i=;i<=len-n;++i)
{
for(int j=;j<=len-n;++j)
{
for(int k=;k<n;++k)
{
if((dp[i][j][k]&&dp[i+k][j+k][n-k])||
(dp[i+k][j][n-k]&&dp[i][j+n-k][k]))
{
dp[i][j][n]=true;
}
}
}
}
}
return dp[][][len];
}
};