字符串的交错组成

字符串的交错组成

题目描述

给定三个字符串str1、str2 和aim,如果aim包含且仅包含来自str1和str2的所有字符，而且在aim中属于str1的字符之间保持原来在str1中的顺序属于str2的字符之间保持原来在str2中的顺序，那么称aim是str1和str2的交错组成。实现一个函数，判断aim是否是str1和str2交错组成，如果是请输出“YES”，否则输出“NO”。

输入描述：

输出三行，分别表示三个字符串$str1$，$str2$ 和 $aim$。$1\le length\left(str1\right),length\left(str2\right)\le 5000,1\le length\left(aim\right)\le 10000$， length()length()表示字符串长度。

输出描述：

输出“YES”或者“NO”。（不包含引号）

示例1

输入

AB
12
1AB2

输出

YES

示例2

输入

2019
9102
22001199

输出

NO

备注：

时间复杂度$O\left(n\ast m\right)$,空间复杂度$O\left(min(n,m)\right)$。（n表示字符串str1长度，m表示s字符串tr2长度）

题解：

又是明显的二维 dp ，设为 F[i, j] ，其含义是：aim[0…i+j-1] 能否被 str1[0…i-1] 和 str2[0…j-1] 交错组成。F[i, j] 有三种情况：

• 如果 F[i-1, j] 为 true 并且 str1[i-1] = aim[i+j-1] ，则 F[i, j] 为 true；
• 如果 F[i, j-1] 为 true 并且 str2[j-1] = aim[i+j-1]，则 F[i, j] 为 true；
• 不满足上面两种情况，则 F[i, j] 为 false。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 5010;
char str1[N];
char str2[N];
char aim[N << 1];
bool f[N][N];
int main(void) {
scanf("%s", str1);
scanf("%s", str2);
scanf("%s", aim);
int len1 = strlen(str1);
int len2 = strlen(str2);
int len = strlen(aim);
if (len != len1 + len2) return 0 * puts("NO");
f[0][0] = true;
for (int i = 1; i <= len1; ++i) {
if (str1[i - 1] == aim[i - 1]) f[i][0] = true;
else break;
}
for (int j = 1; j <= len2; ++j) {
if (str2[j - 1] == aim[j - 1]) f[0][j] = true;
else break;
}
for (int i = 1; i <= len1; ++i) {
for (int j = 1; j <= len2; ++j) {
if ((str1[i - 1] == aim[i + j - 1] && f[i - 1][j]) ||
(str2[j - 1] == aim[i + j - 1] && f[i][j - 1]))
f[i][j] = true;
}
}
return 0 * puts(f[len1][len2] ? "YES" : "NO");
}

滚动数组优化：

直接删掉第一维即可，但是在二重循环中，注意初始化 F[0] 的值。

滚动数组代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 5010;
char str1[N];
char str2[N];
char aim[N << 1];
bool f[N];
int main(void) {
scanf("%s", str1);
scanf("%s", str2);
scanf("%s", aim);
int len1 = strlen(str1);
int len2 = strlen(str2);
int len = strlen(aim);
if (len != len1 + len2) return 0 * puts("NO");
f[0] = true;
for (int i = 1; i <= len2; ++i) {
if (str2[i - 1] != aim[i - 1]) break;
f[i] = true;
}
for (int i = 1; i <= len1; ++i) {
f[0] = f[0] && str1[i - 1] == aim[i - 1];
for (int j = 1; j <= len2; ++j) {
if ((str1[i - 1] == aim[i + j - 1] && f[j]) ||
(str2[j - 1] == aim[i + j - 1] && f[j - 1]))
f[j] = true;
else
f[j] = false;
}
}
return 0 * puts(f[len2] ? "YES" : "NO");
}

注意：

此题效率靠前的解法是不对的，那种遍历两次的解法明显可以 hack ，比如下面两种情况：

abc
abd
abcd
abc
abd
abcdef

两种情况都是 ‘NO’ ，但是按照那种遍历结果都是 ‘YES’，如有 $O(n)$解法，欢迎来讨论。

最后

以上就是怕黑石头为你收集整理的字符串的交错组成的全部内容，希望文章能够帮你解决字符串的交错组成所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。