链接:
判断2个字符串能否组成1个字符串,例如cat和tree能组成tcraete。搜索和DP都可以。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char str1[210],str2[210],str3[420],str4[420]; int len1,len2,len3,n,vis[420],flag; int check(){ int i,count=0; for(i=0;i<len3;i++){ if(!vis[i]) str4[count++]=str3[i]; } str4[count]='\0'; if(!strcmp(str4,str2)) return 1; return 0; } void dfs(int x,int y,int z){ if(x>=len1){ if(check()) flag=1; return; } if(flag) return; if(str1[x]==str3[y]){ vis[y]=1; if(y<len3) dfs(x+1,y+1,z); vis[y]=0; } else{ if(str3[y]!=str2[z]) return; } if(!flag&&y<len3) dfs(x,y+1,z+1); } int main(){ int i; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%s %s %s",str1,str2,str3); len1=strlen(str1); len2=strlen(str2); len3=strlen(str3); if((len1+len2)!=len3){ printf("Data set %d: no\n",i); continue; } if(str1[len1-1]!=str3[len3-1]&&str2[len2-1]!=str3[len3-1]){ printf("Data set %d: no\n",i); continue; } memset(vis,0,sizeof(vis)); flag=0; dfs(0,0,0); if(flag) printf("Data set %d: yes\n",i); else printf("Data set %d: no\n",i); } return 0; }