题意:判断给出的号码是否有是其它号码前缀的情况,有的话输出NO,没有输出YES。
思路:tire树,指针版会超时,所以改用数组模拟。
#include<iostream> using namespace std; struct node { int end; int count; int next[10];//子节点 void init()//初始化 { end=0; count=1; for(int i=0;i<10;i++) next[i]=0; } }tire[100010]; bool flag; int num;//开始把它也写成bool型了 我就晕了 void insert(char *word) { int index=0; int branch,i=0; int len=strlen(word); while(word[i]!='\0') { branch=word[i]-'0'; if(tire[index].next[branch]) { //printf("运行一%d\n",index); index=tire[index].next[branch];//把此节点指向下一个节点(非空节点) tire[index].count++;//下一个节点的字母数++ } else { //printf("运行二%d\n",index); num++;//再开一个新节点 //printf("num=%d\n",num); tire[num].init();//节点初始化 tire[index].next[branch]=num;//把此节点的后继节点指向建立的节点 index=num;//并且把此节点指向新建立的节点 } if(i==len-1) {tire[index].end++;}//单词结束,记录一个单词 if(tire[index].count>1&&tire[index].end==1) {flag=1;}//911,9112可以排除这种情况,因为2节点的count=0. i++; } } int main() { int N,M; char s[15]; scanf("%d",&N); while(N--) { scanf("%d",&M); tire[0].init(); num=0; flag=0; while(M--) { scanf("%s",s); if(!flag) insert(s); } if(flag) printf("NO\n"); else printf("YES\n"); } }