本文主要是介绍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.
思路：
由于一个字符串有很多种二叉表示法，貌似很难判断两个字符串是否可以做这样的变换。
对付复杂问题的方法是从简单的特例来思考，从而找出规律。
先考察简单情况：
字符串长度为1：很明显，两个字符串必须完全相同才可以。
字符串长度为2：当s1="ab", s2只有"ab"或者"ba"才可以。
对于任意长度的字符串，我们可以把字符串s1分为a1,b1两个部分，s2分为a2,b2两个部分，满足（(a1~a2) && (b1~b2)）或者 （(a1~b2) && (a1~b2)）
可以由递归和三维动态规划两种方法。
对付复杂问题的方法是从简单的特例来思考，从而找出规律。
先考察简单情况：
字符串长度为1：很明显，两个字符串必须完全相同才可以。
字符串长度为2：当s1="ab", s2只有"ab"或者"ba"才可以。
对于任意长度的字符串，我们可以把字符串s1分为a1,b1两个部分，s2分为a2,b2两个部分，满足（(a1~a2) && (b1~b2)）或者 （(a1~b2) && (a1~b2)）
可以由递归和三维动态规划两种方法。
动态规划定义：
- f[i][j][k] as: if s1(i, i+k-1) and s2(j, j+k-1) are scramble
- 0<subLen<k,f[i][j][k]|=f[i][j][subLen]&&f[i+subLen][j+subLen][k-subLen]或者f[i][j][k]|=f[i][k-subLen+j][subLen]&&f[i+subLen][j][k-subLen]
代码：
bool Recursive( string s1, string s2 )
{
//throw std::exception("The method or operation is not implemented.");
if(s1.size() != s2.size()) return false;
vector<int> cnt(256, 0);
for(int i = 0; i < s1.size(); ++i)
cnt[s1[i]]++;
for(int i = 0; i < s2.size(); ++i)
cnt[s2[i]]--;
for(int i = 0; i < cnt.size(); ++i)
if(cnt[i] != 0) return false;
int n = s1.size();
if(n == 1) return true;
//partition
for (int i = 1; i < n; ++i)//i is the size of one sub tree
{
if( Recursive( s1.substr(0, i), s2.substr(0, i) ) && Recursive( s1.substr(i, n-i), s2.substr(i, n-i) )
|| Recursive( s1.substr(0, i), s2.substr(n-i, i) ) && Recursive( s1.substr(i, n-i), s2.substr(0, n-i) ) )
return true;
}
return false;
}
bool DP(string s1, string s2)
{
if(s1.size() != s2.size()) return false;
int n = s1.size();
vector<vector<vector<bool>>> f(n, vector<vector<bool>>(n, vector<bool>(n+1, false) ) );
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
f[i][j][1] = s1[i]==s2[j];
}
}
for (int k = 2; k <= n; ++k)
{
for (int i = 0; i+k-1 < n; ++i)
{
for (int j = 0; j+k-1 < n; ++j)
{
for (int subLen = 1; subLen < k; ++subLen)
{
if(f[i][j][subLen]&&f[i+subLen][j+subLen][k-subLen]
|| f[i][k-subLen+j][subLen]&&f[i+subLen][j][k-subLen])
{
f[i][j][k] = true;
break;
}
}
}
}
}//end of dp
return f[0][0][n];
}
这篇关于Scramble String的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
