解题思路: 每个字符为单位建立一棵Trie树
字符串结尾的结点用w标记，然后插入时判断两种情况：
每次插入时如果经过之前插入字符串的结尾，则之前插入的字符串必定是前缀
每次插入时如果插到结尾还在之前的结点中，则现在插入的字符串必定是前缀
字典树的两种写法：
1.结点中包含next[ ]，加快查找时间，但耗费大量的空间
2.结点中不包含next[ ]，类似与建立有向图利用pre[ ]遍历，查找时间慢些，但省下很多空间
代码:
#include#include #include #define MAX 10100 struct snode{ char ch1; int next,w; //第二种写法 }Tree[MAX*100]; char ch[20]; int pd,Index,pre[MAX*100]; void Add_edge(int a,char ch2,int len,int Tlen) //建立有向图 { Tree[Index].ch1=ch2,Tree[Index].next=pre[a]; if(len==Tlen) Tree[Index].w=1; pre[a]=Index++; } void DFS(int Star,int len,int Tlen,int kk) //DFS遍历 { int i; if(len>Tlen||pd) return ; if(Tree[Star].w==1) { pd=1; return ; } for(i=pre[Star];i!=-1;i=Tree[i].next) { if(Tree[i].ch1==ch[len-1]) //遍历之前插入的点 { if(Tree[i].w==1) //小对大 { pd=1; return ; } if(len==Tlen) { pd=1; return ; } DFS(i,len+1,Tlen,kk); return ; } } if(Tree[Star].w&&i==-1&&kk!=1) //找到结尾结点 { pd=1; return; } Add_edge(Star,ch[len-1],len,Tlen); DFS(Index-1,len+1,Tlen,kk); } int main() { int t,n,i; scanf("%d",&t); while(t--) { pd=0; Index=1; memset(pre,-1,sizeof(pre)); memset(Tree,0,sizeof(Tree)); Tree[0].ch1='\0'; Tree[0].next=-1; Tree[0].w=0; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%s",ch); if(!pd) //找到前缀则停止搜索 { DFS(0,1,strlen(ch),i); } } if(pd) printf("NO\n"); else printf("YES\n"); } return 0; }