MIOJ #6 交叉队列

描述

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

    }
}

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注