交替字符串

2022-01-01 算法

交替字符串题目详情: 如果字符串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

思路：不断取str3中的字母匹配str1和str2。a,b,c分别代表指向字符串的位置，如果匹配则一直往下，否则返回。
由于不匹配的情况不会递归太久就会返回，所以不会超时。

#include #includeconst int N=102; char str1[N],str2[N],str3[2*N]; int goal; void dfs(int a,int b,int c){ if(!str3[c]||goal){ goal=1; return; } if(str1[a]==str3[c]) dfs(a+1,b,c+1); if(str2[b]==str3[c]) dfs(a,b+1,c+1); } int main(){ while(~scanf("%s %s %s",str1,str2,str3)){ int len1=strlen(str1),len2=strlen(str2),len3=strlen(str3); if(len1+len2!=len3){ printf("NO\n"); continue; } int a=0,b=0,c=0; goal=0; dfs(a,b,c); printf("%s\n",goal?"YES":"NO"); } return 0; }

推荐阅读

上一篇：学习笔记——|学习笔记—— unreferenced local variable

下一篇：MacOS安装Python环境