2022年12月版

class Solution {
public:
bool isScramble(string s1, string s2) {
bool dp[31][30][30] = { false };
for (int i = 0; i < s1.length(); i++)
{
for (int j = 0; j < s2.length(); j++)
{
dp[1][i][j] = s1[i] == s2[j];
}
}
for (int len = 2; len <= s1.length(); len++)
{
for (int i = 0; i+len-1 < s1.length(); i++)
{
for (int j = 0; j + len - 1 < s2.length(); j++)
{
bool b = false;
for (int m = 1; m < len; m++)
{
if (dp[m][i][j] && dp[len - m][i + m][j + m])
{
b = true;
}
if (dp[m][i][j + len - m] && dp[len - m][i + m][j])
{
b = true;
}
}
dp[len][i][j] = b;
}
}
}
return dp[s1.length()][0][0];
}
};

2023年6月版

class Solution {
public:
bool isScramble(string s1, string s2) {
m_c = s1.length();
vector < vector> vLenBegin1Begin2(m_c + 1, vector(m_c, vector(m_c,true)));
for (int b1 = 0; b1 < m_c; b1++)
{
for (int b2 = 0; b2 < m_c; b2++)
{
vLenBegin1Begin2[1][b1][b2] = s1[b1] == s2[b2];
}
}
for (int len = 2; len <= m_c; len++)
{
for (int b1 = 0; b1 + len - 1 < m_c; b1++)
{
for (int b2 = 0; b2 + len - 1 < m_c; b2++)
{
bool bSame = false;
for (int leftLen = 1; leftLen < len; leftLen++)
{
const int iRightLen = len - leftLen;
//不改变位置
const int tmp = vLenBegin1Begin2[leftLen][b1][b2] && vLenBegin1Begin2[len - leftLen][b1 + leftLen][b2 + leftLen];
bSame |= tmp;
//改变位置
const int tmp2 = vLenBegin1Begin2[leftLen][b1][b2 + iRightLen] && vLenBegin1Begin2[iRightLen][b1 + leftLen][b2];
bSame |= tmp2;
}
vLenBegin1Begin2[len][b1][b2] = bSame;
}
}
}
return vLenBegin1Begin2.back()[0][0];
}
int m_c;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

class="table-box">
我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

data-report-view="{"mod":"1585297308_001","spm":"1001.2101.3001.6548","dest":"https://blog.csdn.net/he_zhidan/article/details/135360259","extend1":"pc","ab":"new"}">> id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"> class="blog_extension blog_extension_type5" id="blog_extension"> class="extension_official" data-report-click="{"spm":"1001.2101.3001.6471"}" data-report-view="{"spm":"1001.2101.3001.6471"}"> class="blog_extension_card_left"> class="blog_extension_card_cont"> 群中有博文配套源码 class="blog_extension_card_cont_r"> QQ群名片
注:本文转载自blog.csdn.net的Ocean@上源码的文章"https://blog.csdn.net/qq_34253002/article/details/134332705"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接

评论记录:

未查询到任何数据!