描述
给出三个队列 s1，s2，s3 ，判断 s3 是否是由 s1 和 s2 交叉得来。 如：s1 为 aabcc ， s2 为 dbbca。 当 s3 为 aadbbcbcac 时，返回 true（即将 s1 拆成三部分： aa，bc，c 分别插入 s2 对应位置） 否则返回 false。
输入
aabcc,dbbca,aadbbcbcac
输出
true
输入样例
aabcc,dbbca,aadbbcbcac aabcc,dbbca,aadbbbaccc a,b,ab a,b,ba a,b,ac abc,bca,bcaabc abc,bca,aabbcc
输出样例
true false true true false true false
AC代码：
#include <bits/stdc++.h>
#include<list>
#include<vector>
using namespace std;
bool crossQueue(string s)
{
int a = 0,b = 0,c = 0;
int cnt = 0;
a = 0;
cnt = 0;
for(int i = 0; i<s.length(); i++)
{
if(s[i] == ',' )
{
if(cnt == 0)
{
b = i;
cnt++;
}
else
{
c= i;
}
}
}
string arr1 = s.substr(a,b);
string arr2 = s.substr(b+1,c-b-1);
string arr3 = s.substr(c+1,s.length()-c-1);
int len1 = arr1.length();
int len2 = arr2.length();
int len3 = arr3.length();
if(len3 != len1 + len2)
{
return false;
}
if(len1 == 0)
{
return (arr2 == arr3);
}
if(len2 == 0)
{
return (arr1 == arr3);
}
int dp[len1+1][len2+1];
memset(dp,0,sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= len1; i++)
{
if (arr1[i-1] == arr3[i-1])
dp[i][0] = dp[i - 1][0];
}
for (int i = 1; i <= len2; i++)
{
if (arr2[i-1] == arr3[i-1])
dp[0][i] = dp[0][i - 1];
}
for (int i = 1; i < len1 + 1; i++)
{
for (int j = 1; j < len2 + 1; j++)
{
int t = i + j;
if (arr1[i-1] == arr3[t-1])
{
dp[i][j] = dp[i - 1][j] || dp[i][ j];
}
if (arr2[j-1] == arr3[t-1])
{
dp[i][j] = dp[i][j - 1] || dp[i][j];
}
}
}
/* for(int i = 0;i<len1+1;i++){
for(int j = 0;j<len2+1;j++){
cout<<dp[i][j]<<" ";
}
cout<<endl;
}*/
if (dp[len1][len2] == 1)
{
return true;
}
else return false;
}
int main()
{
string s;
while(cin>>s)
{
if(crossQueue(s))
{
cout<<"true"<<endl;
}
else cout<<"false"<<endl;
}
}
