给你n个数字，若这些字符串中有字符串成为一个其他字符串的前缀，输出no，否则输出yes。
考虑用字典树存所有字符串，然后遍历一遍，对当前字符串在建好的字典树上查找，若在结尾处的cnt值不等于1，则证明从根到当前字符至少是另一个字符的前缀，符合题意的NO。
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int maxn=1e4+5; int t,n; char str[maxn][15]; struct node{ int cnt; struct node *next[26]; node(){ cnt=0; memset(next,0,sizeof(next)); } }; node *root; void buildtrie(char *s){ node *p=root; node *tmp=NULL; int len=strlen(s); for(int i=0;i<len;i++){ if(p->next[s[i]-‘0‘]==NULL){ tmp=new node; p->next[s[i]-‘0‘]=tmp; } p=p->next[s[i]-‘0‘]; p->cnt++; } } bool findtrie(char *s){ int len=strlen(s); node *p=root; for(int i=0;i<len;i++){ p=p->next[s[i]-‘0‘]; } if(p->cnt!=1) return 0; return 1; } void del(node *root){ for(int i=0;i<26;i++){ if(root->next[i]) del(root->next[i]); } delete(root); } int main() { scanf("%d",&t); while(t--){ root = new node; scanf("%d",&n); for(int i = 1; i <= n; i++){ scanf("%s",str[i]); buildtrie(str[i]); } int flag = 1; for(int i = 1; i <= n; i++){ if(findtrie(str[i])==0){ flag = 0; break; } } if(flag) printf("YES\n"); else printf("NO\n"); del(root); } return 0; }
原文：https://www.cnblogs.com/qq2210446939/p/13388148.html