LeetCode 87. Scramble String
LeetCode 87. Scramble String
ShenduCC
发布于 2019-12-04 09:53:40
发布于 2019-12-04 09:53:40
一开始我读错了题意，以为是二分，
结果却是动态规划的区间DP
我都状态数组是dp[i1][j1][i2][j2]，表示第一个字符串的i1到j1区间和第二个字符串的i2到j2区间，是符合条件，是可以旋转转换的。
string最大的长度也不过50多个吧。
所以险过。
状态转移方程，很简单啦，将区间划分，有两种情况，一种是交换子树，一种是没交换。判断划分区间后的子区间
if(dp[i1][i1+k][i2][i2+k]==1
&&dp[i1+k+1][j1][i2+k+1][j2]==1)
{
dp[i1][j1][i2][j2]=1;
}
if(dp[i1][i1+k][j2-k][j2]==1
&&dp[i1+k+1][j1][i2][j2-k-1]==1)
{
dp[i1][j1][i2][j2]=1;
}k就是划分的区间。
完整的c++代码
class Solution {
public:
int dp[55][55][55][55];
bool isScramble(string s1, string s2) {
int len1 = s1.length();
int len2 = s2.length();
for(int l=0;l<len1;l++)
{
for(int i1=0;i1+l<len1;i1++)
{
int j1=i1+l;
for(int i2=0;i2+l<len2;i2++)
{
int j2=i2+l;
if(l==0)
{
if(s1[i1]==s2[i2])
{
dp[i1][j1][i2][j2]=1;
}
}
else
{
for(int k=0;k<l;k++)
{
if(dp[i1][i1+k][i2][i2+k]==1
&&dp[i1+k+1][j1][i2+k+1][j2]==1)
{
dp[i1][j1][i2][j2]=1;
break;
}
if(dp[i1][i1+k][j2-k][j2]==1
&&dp[i1+k+1][j1][i2][j2-k-1]==1)
{
dp[i1][j1][i2][j2]=1;
break;
}
}
}
}
}
}
if(dp[0][len1-1][0][len2-1]==1)
return true;
else
return false;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-12-02 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读