hdu1671Phone List - 字典樹

hdu1671Phone List
簡單的字典樹
空間換時間，花銷超大，，，如果有多組數據的話 呃
那用完就釋放吧 ， 恩 。
[cpp] 
#include<iostream> 
using namespace std; 
 
struct trie 
{ 
    bool exist; 
    int num; 
    trie *next[10]; 
    trie() 
    { 
        exist=0; 
        num=0; 
        for(int i=0;i<10;i++) next[i]=0; 
    } 
} *root; 
 
bool insert(trie *p,char *s) 
{ 
    int k=0; 
    while(s[k]!='\0') 
    { 
        if(!p->next[s[k]-'0']) p->next[s[k]-'0']=new trie; 
        p=p->next[s[k++]-'0']; 
         
        if(p->exist) return 0;            //如果此前綴為電話號碼，，輸出"NO" 
        p->num++; 
    } 
    p->exist=1; 
    if(p->num>1)  return 0;               //之前有號碼路過的說，， 
     
    return 1; 
} 
 
void Free(trie *p) 
{ 
    for(int i=0;i<10;i++) 
        if(p->next[i]) Free(p->next[i]); 
    if(p)  delete p; 
} 
 
int main() 
{ 
    int T,n,i; 
    bool Success; 
    char t[11]; 
    scanf("%d",&T); 
    while(T--) 
    { 
        root=new trie; 
        Success=1; 
        scanf("%d",&n); 
        for(i=1;i<=n;i++) 
        { 
            scanf("%s",t); 
            if(!insert(root,t)) {Success=0; i++;break;} 
        } 
        for(;i<=n;i++) scanf("%s",t); 
        printf(Success?"YES\n":"NO\n"); 
        Free(root); 
    } 
    return 0; 
}