CSDN编程挑战——《交替字符串》
2024-09-20 21:38:31
交替字符串
题目详情:
假设字符串str3可以由str1和str2中的字符按顺序交替形成,那么称str3为str1和str2的交替字符串。比如str1="abc",str2="def"。那么"adbecf", "abcdef", "abdecf", "abcdef", "adefbc"等等都为str1和str2的交替字符串。更形式化的。str3的生成算法例如以下:
str3=""
while str1不为空 or str2不为空:
把str1或str2的首字符增加到str3,并从str1或str2中删除对应的字符
end
给定str1, str2,和str3。推断str3是否为str1和str2的交替字符串。
输入格式:
多组数据,每组数据三行,各自是str1,str2,str3。str1,str2的长度在[1..100]范围内,str3的范围在[1..200]范围内。字符串仅仅包括小写英文字母。
输出格式:
每组数据输出一行YES或者NO。
答题说明:
输入例子
a
b
ab
a
b
ca
输出例子:
YES
NO
欠缺考虑(Error):
#include "stdio.h"
#include "string.h"
#define maxn 100+2 char str1[maxn],str2[maxn],str3[maxn*2]; int fun()
{
int i1=0,size1=strlen(str1);
int i2=0,size2=strlen(str2);
int i3=0,size3=strlen(str3); //通过 str1和str2 顺序匹配 str3 ,匹配不到 return 0
while(i3<size3){
if(i1<size1 && str3[i3]==str1[i1]){
i1++;
}else if(i2<size2 && str3[i3]==str2[i2]){
i2++;
}else {
return 0;
}
i3++;
} return 1;
} int main()
{
while(scanf("%s%s%s",str1,str2,str3))
{
if(strlen(str1)+strlen(str2)==strlen(str3) && fun()){
printf("YES\n");
}else{
printf("NO\n");
}
} return 0;
}
/*
不通过的測试用例:
12345 6278 162782345 错误原因:
通过 str1和str2 按顺序进行匹配 str3 。此程序的错就错在匹配这。 即 str1和str2 对(str3中)某一个字符同一时候能够匹配时没有进行选 择而是简单的用 str1中的字符去匹配
*/
改动后(AC):
#include "stdio.h"
#include "string.h"
#define maxn 100+2 char str1[maxn],str2[maxn],str3[maxn*2]; int fun(int i1,int i2,int i3)
{
if(i1>strlen(str1) || i2>strlen(str2) || i3>strlen(str3)) return 0; if(i1==strlen(str1) && i2==strlen(str2) && i3==strlen(str3)){
return 1;
}else if(str1[i1]==str2[i2] && str3[i3]==str1[i1]){
return (fun(i1+1,i2,i3+1) || fun(i1,i2+1,i3+1));
}else if(str3[i3]==str1[i1]){
return fun(i1+1,i2,i3+1);
}else if(str3[i3]==str2[i2]){
return fun(i1,i2+1,i3+1);
}else{
return 0;
}
} int main()
{
while(scanf("%s%s%s",str1,str2,str3))
{
if(strlen(str1)+strlen(str2)==strlen(str3) && fun(0,0,0)){
printf("YES\n");
}else{
printf("NO\n");
}
} return 0;
}
CSDN挑战编程交流群: 372863405
最新文章
- (转载)哈夫曼编码(Huffman)
- 算法: 斐波那契数列C/C++实现
- Subversion与TortoiseSVN的安装
- python-day3-集合
- UITextfiled子视图被剪切
- 这是html5中WebGL的演示
- [技术翻译]构建现代化的 Objective-C (上)
- HDU - 1248 寒冰王座 数学or暴力枚举
- mysql 原理~ FTWRDL
- css3 二维码 添加 扫描特效
- 第十二周(MySort)
- 在 Confluence 6 中连接一个 LDAP 目录
- introduction to python for statistics,analysis笔记2
- IOS-如何优雅地拦截按钮事件(判断是否需要登录)
- 删除docker网络docker0
- 流畅的python第十五章上下文管理器和else块学习记录
- pip 查看已安装模块、卸载指定模块、安装指定版本模块
- Unity GUI自适应屏幕分辨率(一)布局自适应
- Scala学习笔记(四):从文件里读取文本行
- OSSIM 4 组件目录
热门文章
- BZOJ2118: 墨墨的等式(最短路构造/同余最短路)
- 进阶攻略|最全的前端开源JS框架和库
- 【习题 7-9 UVA-1604】Cubic Eight-Puzzle
- 疯狂html5讲义(二):HTML5简的经常使用元素与属性(二):html5新增的通用属性
- java 之 wait, notify, park, unpark , synchronized, Condition
- Android 使用Wake Lock
- 1.html+css页面设计
- .v 和 .sdf
- How to Rotate Tomcat catalina.out
- 洛谷——P1035 级数求和