描述

给出三个队列 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;

    }
}