题目和分析来自于https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/05.04.md
题目描述
输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交错而成，即不改变s1和s2中各个字符原有的相对顺序，例如当s1 = “aabcc”，s2 = “dbbca”，s3 = “aadbbcbcac”时，则输出true，但如果s3=“accabdbbca”，则输出false。
分析
按照原文的分析，考察的是动态规划的知识。
不过原文里的代码，我看着有点奇怪，感觉是错的。
我试了试，dp矩阵打印出来确实是错的。
下面是我改写的，dp矩阵的第0行，还有第0列，都是单独拿出来初始化的，dp[ii][0] = true 含义是string s1[0...ii-1] 在string s2为空的情况下，和string s3[0...ii-1]相等；
【编程艺术|编程艺术（：交替字符串 C++语言）】同理可得dp[0][jj]的含义。
#include
#include
using namespace std;
bool isInterleave(string &s1, string &s2, string &s3)
{
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
if (len1 + len2 != len3)
{
return false;
}
if (0 == len1)
{
return (s2 == s3) ? true : false;
}
if (0 == len2)
{
return (s1 == s3) ? true : false;
}
// allocating memory to store middle values
// we need a bias to get started
bool ** dp = new bool*[len1+1];
for (int ii = 0; ii < len1+1; ++ii)
{
dp[ii] = new bool [len2+1];
}
// dp[ii][jj]== true means that
// s1[0...ii-1] and s2[0...jj-1] forming s3[0...(ii+jj-1)] is true
// dp[0][0] means two null string form a null string, which is true
dp[0][0] = true;
for (int ii = 1; ii < len1+1; ++ii)
{
dp[ii][0] = (s1.substr(0,ii) == s3.substr(0,ii)) ? true : false;
}
for (int jj = 1; jj < len2+1; ++jj)
{
dp[0][jj] = (s2.substr(0,jj) == s3.substr(0,jj)) ? true : false;
}
for (int ii = 1; ii < len1+1; ++ii)
{
for (int jj = 1; jj < len2+1; ++jj)
{
if ((dp[ii-1][jj] && s1[ii - 1] == s3[ii+jj-1]) ||
(dp[ii][jj-1] && s2[jj - 1] == s3[ii+jj-1]) )
{
dp[ii][jj] = true;
}else
{
dp[ii][jj] = false;
}
}
}
//for (int ii = 0; ii < len1+1; ++ii)
//{
//for (int jj = 0; jj < len2+1; ++jj)
//{
////check char s3[ii+jj-1]
//if (dp[ii][jj] ||
//((ii - 1 > 0) && dp[ii-1][jj] && s1[ii - 1] == s3[ii+jj-1]) ||
//((jj - 1 > 0) && dp[ii][jj-1] && s2[jj - 1] == s3[ii+jj-1]) )
//{
//dp[ii][jj] = true;
//}else
//{
//dp[ii][jj] = false;
//}
//}
//}
cout << "dp matrix:" << endl;
for (int ii = 0; ii < len1 + 1; ++ii)
{
for (int jj = 0; jj < len2 + 1; ++jj)
{
cout << dp[ii][jj] << " ";
}
cout << endl;
}
bool result = dp[len1][len2];
for (int ii = 0; ii < len2+1; ++ii)
{
delete [] dp[ii];
}
delete [] dp;
return result;
}
int main()
{
string s1 = "aabcce", s2 = "dbbca";
string s3 = "aadbbcbcace";
if (isInterleave(s1, s2, s3))
{
cout << "yes" << endl;
}else
{
cout << "no" << endl;
}
}
推荐阅读
- 个人日记|K8s中Pod生命周期和重启策略
- 学习分享|【C语言函数基础】
- C++|C++浇水装置问题
- 数据结构|C++技巧（用class类实现链表）
- C++|从零开始学C++之基本知识
- 步履拾级杂记|VS2019的各种使用问题及解决方法
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- 动态规划|暴力递归经典问题
- 麦克算法|4指针与队列
- 遇见蓝桥遇见你|小唐开始刷蓝桥（一）2020年第十一届C/C++ B组第二场蓝桥杯省赛真题