Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order. For example, consider forming "tcraete" from "cat" and "tree": String A: cat String B: tree String C: tcraete As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming "catrtee" from "cat" and "tree": String A: cat String B: tree String C: catrtee
Finally, notice that it is impossible to form "cttaree" from "cat" and "tree".
3
cat tree tcraete
cat tree catrtee
cat tree cttaree
Data set 1: yes
Data set 2: yes
Data set 3: no
简单的dp写法,用一个二维数组,第一维代表第一个字符串用了前几位,第二维代表第二个字符串用了前几位,若 dp[i][j] 可以组成 str[i+j]之前的所有字符,则为1,否为0。 例子: abc def adebcf dp为1的状态都有: dp[1][0] = 1; 取str1[0] dp[1][1] = 1; 在dp[1][0]的基础上再取str2[0],以此类推 dp[1][2] = 1; dp[2][2] = 1; dp[3][2] = 1; dp[3][3] = 1;
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<deque>
#include<cstdlib>
#include<fstream>
#include<map>
#include<iomanip>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<list>
typedef long long ll;
using namespace std;
string str1,str2,str;
int dp[440][440];
int main()
{
int T;
scanf("%d", &T);
for(int k=0;k<T;k++)
{
cin>>str1>>str2>>str;
int l1=str1.length(),
l2=str2.length(),
l=str.length();
printf("Data set %d: ", k+1);
if(l!=l1+l2)
{
cout<<"no"<<endl;
continue;
}
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=0;i<=l1;i++)
{
for(int j=0;j<=l2;j++)
{
if(i==0 && j==0) continue;
if(i!=0 && dp[i-1][j]==1 && str1[i-1]==str[i+j-1])
{
dp[i][j]=1;
continue;
}
if(j!=0 && dp[i][j-1]==1 && str2[j-1]==str[i+j-1])
{
dp[i][j]=1;
}
}
}
if(dp[l1][l2]==1) cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
return 0;
}