题目：点击打开链接
题意：给一堆电话号码，是否某个电话号码是其中一个电话号码的前缀，如果有则不能打通 ，输出NO ，没有就全部能连通 ，输出YES。
套模板就可以了，注意要释放内存。
#include<iostream> #include<string> #include<cstring> #include<cstdio> using namespace std; struct Tire { int num; //存储以当前字符串为前缀的字符串的数量 Tire *next[10]; Tire() { num=0; memset(next,0,sizeof(next)); } }*root; char s[10005][20]; void insert(char *s) { Tire *p=root; for(int i=0;s[i];i++) { int index=s[i]-'0'; if(!p->next[index]) p->next[index]=new Tire; p=p->next[index]; p->num++; } } int find(char *s) { Tire *p=root; for(int i=0;s[i];i++) { int index=s[i]-'0'; p=p->next[index]; } if(p->num>1) return 1; //如果这个号码出现了两次或以上，则肯定是某个号码的前缀 else return 0; } void del(Tire *T) { for(int i=0;i<10;i++) { if(T->next[i]!=NULL) del(T->next[i]); } delete T; } int main() { // freopen("E:\\ACM\\test.txt","r",stdin); int T,n; cin>>T; while(T--) { root=new Tire; //记得先申请空间 cin>>n; for(int i=0;i<n;i++) { cin>>s[i]; insert(s[i]); } int flag=0; for(int i=0;i<n;i++) { flag=find(s[i]); if(flag==1) break; } if(flag) puts("NO"); else puts("YES"); del(root); //释放内存 } return 0; }
