题目链接:http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=1174

题目很简单,依然是前缀字符串的题,用普通循环排序超时了,后来改成快速排序就ok了,另外由于将两个字符串相同的情况也考虑了导致WA了几次,我晕,考虑不够仔细啊!

我的思路:先将字符串按从小到大排序,然后依次判断前一个字符串是否是下一个的子串,若是就break,输出NO……

代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char string[10001][20],p[20];
int cmp(const void*a,const void*b)
{
return strcmp((char*)a,(char*)b);
}
int judge(int n)//用来判断案例是否满足要求
{
int i,j,n1,n2,flag=0;
for(i=1;i<n;i++)
{
n1=strlen(string[i-1]);
n2=strlen(string[i]);
if(n1<n2)
{
for(j=0;j<n1;j++)
if(string[i-1][j]!=string[i][j])
break;
if(j==n1)
return 0;
}
}
return 1;
}
int main()
{
int N,flag,i,j,n;
scanf(“%d”,&N);
for(i=0;i<N;i++)
{
scanf(“%d”,&n);
getchar();
memset(string,0,sizeof(string));
for(j=0;j<n;j++)
gets(string[j]);
qsort(string,n,sizeof(char)*20,cmp);//快速排序
flag=judge(n);//判断并返回
if(flag==1)
printf(“YES\n”);
else
printf(“NO\n”);
}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation