[Trie]Hdu 1671 Phone List

This is my first problem of Trie.

Thanks to http://www.cnblogs.com/dolphin0520/archive/2011/10/15/2213752.html

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
 
using namespace std;
 
int t,n;
bool ok;
string str;
 
struct Trie  
{  
    Trie *next[10];  
    bool over;  
};  
 
void insert(Trie * root ,string str){
    int len=str.length();
    //cout<<"len="<<len<<endl;
    Trie * p= root;
    for(int i=0;i<len;++i){
        //cout<<str[i]-'0'<<" ";
        if(p->next[ str[i]-'0' ] ==NULL){
            Trie * temp=new Trie;
            temp->over=false;
            for(int j=0;j<10;++j){
                temp->next[j]=NULL;
            }
            p->next[ str[i]-'0' ]=temp;
        }
        if(p->over==true)ok=false;
        p=p->next[ str[i]-'0' ];
    }
    p->over=true;
    for(int i=0;i<10;++i){
        if(p->next[i]!=NULL) {
            ok=false;
            break;
        }
    }   
}
void del(Trie * root){
    Trie*temp=root;
    for(int i=0;i<10;++i){
        if(temp->next[i]!=NULL){
            del(temp->next[i]);
        }
    }
    delete(root);
}
int main()
{
    cin>>t;
    while(t--){
        //init
        ok=true;
        Trie *root=new Trie;
        root->over=false;
        for(int i=0;i<10;++i){
            root->next[i]=NULL;
        }
 
        //get data
        cin>>n;
        while(n--){
            cin>>str;
            insert(root,str);
        }
 
        if(ok)puts("YES");
        else puts("NO");
        del(root);
    }
     
    return 0;
}           

  

原文地址:https://www.cnblogs.com/bruce27/p/4579157.html