字符串的交错组成
题目描述
给定三个字符串str1、str2 和aim,如果aim包含且仅包含来自str1和str2的所有字符，而且在aim中属于str1的字符之间保持原来在str1中的顺序属于str2的字符之间保持原来在str2中的顺序，那么称aim是str1和str2的交错组成。实现一个函数，判断aim是否是str1和str2交错组成，如果是请输出“YES”，否则输出“NO”。
输入描述：
输出三行，分别表示三个字符串 s t r 1 str1 str1， s t r 2 str2 str2 和 a i m aim aim。 1 ≤ l e n g t h ( s t r 1 ) , l e n g t h ( s t r 2 ) ≤ 5000 , 1 ≤ l e n g t h ( a i m ) ≤ 10000 1 leq lengthleft ( str1 right ),lengthleft ( str2 right ) leq 5000 ,1 leq lengthleft(aim right) leq10000 1≤length(str1),length(str2)≤5000,1≤length(aim)≤10000， length()length()表示字符串长度。
输出描述：
输出“YES”或者“NO”。（不包含引号）
示例1
输入
1
2
3
4AB 12 1AB2
输出
1
2YES
示例2
输入
1
2
3
42019 9102 22001199
输出
1
2NO
备注：
时间复杂度 O ( n ∗ m ) Oleft( n*m right) O(n∗m),空间复杂度 O ( m i n ( n , m ) ) Oleft( min(n,m) right) O(min(n,m))。（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。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35#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] 的值。
滚动数组代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34#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 ，比如下面两种情况：
1
2
3
4
5
6
7abc abd abcd abc abd abcdef
两种情况都是 ‘NO’ ，但是按照那种遍历结果都是 ‘YES’，如有 O ( n ) O(n) O(n)解法，欢迎来讨论。
最后
以上就是怕黑石头最近收集整理的关于字符串的交错组成的全部内容，更多相关字符串内容请搜索靠谱客的其他文章。
发表评论 取消回复