Common Permutation

Common Permutation

时间: 1ms        内存:64M

描述:

Given two strings a and b, print the longest string x of letters such that there is a permutation of x that is a subsequence of a and there is a permutation of x that is a subsequence of b.

输入:

The input file contains several cases, each case consisting of two consecutive lines. This means that lines 1 and 2 are a test case, lines 3 and 4 are another test case, and so on. Each line contains one string of lowercase characters, with first line of a pair denoting a and the second denoting b. Each string consists of at most 1,000 characters.

输出:

For each set of input, output a line containing x. If several x satisfy the criteria above, choose the first one in alphabetical order

示例输入:

pretty
women
walking
down
the
street

示例输出:

e
nw
et

提示:

参考答案(内存最优[752]):

#include<stdio.h>
#include<string.h>
int main()
{
	int k,j;
	char a[1000],b[1000],i;
	do
	{		
		gets(a);
		gets(b);
		for(i='a';i<='z';i++)
		{
			for(j=0;j<strlen(a);j++)
			{
				if(a[j]==i)
				{
					for(k=0;k<strlen(b);k++)
					{
						if(b[k]==a[j])
						{
							printf("%c",i);
							break;
						}
					}
					break;
				}
			}
		}
		printf("\n");
	}while(scanf("%d",&a)!=EOF);
	return 0;
}

参考答案(时间最优[0]):

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int a[300];
int main()
{
    char c[80],d[80];
    while(gets(c))
    {
        gets(d);
        memset(a,0,sizeof(a));
        for(int i=0; i<strlen(c); i++)
            for(int j=0; j<strlen(d); j++)
                if(c[i]==d[j])a[c[i]]++;
        for(int i=65; i<130; i++)
            if(a[i])printf("%c",i);
        printf("\n");
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

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