首页 > 代码库 > hdu1671Phone List(字典树)
hdu1671Phone List(字典树)
#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> using namespace std; typedef struct Node { struct Node *next[10]; int flag; }Node,*Tree; int flag1; void Creat(Tree &T) { T=(Node *)malloc(sizeof(Node)); T->flag=0; for(int i=0;i<10;i++) T->next[i]=NULL; } void insert(Tree &T,char *s) { Tree p=T; int t; int l=strlen(s); for(int i=0;i<l;i++) { t=s[i]-‘0‘; if(p->next[t]==NULL) Creat(p->next[t]); p=p->next[t]; if(p->flag>0) flag1=0; } p->flag++; } void D(Tree p) { for(int i=0;i<10;i++) { if(p->next[i]!=NULL) D(p->next[i]); } free(p); } int cmp(const void *a,const void *b) { return strcmp((char *)a,(char *)b); } char a[10001][30]; int main() {
Tree T; int tt,m; scanf("%d",&tt); while(tt--) { Creat(T); flag1=1; scanf("%d",&m); for(int i=0;i<m;i++) { scanf("%s",a[i]);
} qsort(a,m,sizeof(a[0]),cmp); for(int i=0;i<m;i++) {
insert(T,a[i]); } if(flag1) printf("YES\n");
else printf("NO\n"); D(T);
} return 0; }