hdu 1671 Phone List (字典树)

# include <cstdio>
# include <algorithm>
# include <cstring>
# include <iostream>
# include <map>
# define MAX 15
using namespace std;
typedef struct Trie_Node
{
    bool flag;//是否有子树
    struct Trie_Node *next[MAX];
}Trie;
void Insert(Trie *root,char *str)
{
    Trie *p=root;
    int len=strlen(str);
    for(int i=0;i<len;i++)
    {
        if(p->next[str[i]-'0']==NULL)
        {
            Trie *temp=(Trie*)malloc(sizeof(Trie));
            for(int j=0;j<MAX;j++)
                temp->next[j]=NULL;
            temp->flag=false;
            p->next[str[i]-'0']=temp;
            p->flag=true;
        }
        p=p->next[str[i]-'0'];
    }
}
bool find(Trie *root,char *str)
{
    Trie *p=root;
    int len=strlen(str);
    for(int i=0;i<len;i++)
    {
        if(p->next[str[i]-'0']==NULL)
            return false;
        p=p->next[str[i]-'0'];
    }
    return p->flag;
}
void del(Trie *root)//释放空间
{
    for(int i=0;i<MAX;i++)
    {
        if(root->next[i]!=NULL)
            del(root->next[i]);
    }
    free(root);
}
int main()
{
    int t,n,i;
    char str[10010][15];
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            scanf("%d",&n);
            Trie *root=(Trie*)malloc(sizeof(Trie));
            for(i=0;i<MAX;i++)
                {
                    root->next[i]=NULL;
                }
            root->flag=false;
            for(i=0;i<n;i++)
            {
                scanf("%s",str[i]);
                Insert(root,str[i]);
            }
            for(i=0;i<n;i++)
            {
                if(find(root,str[i]))
                    break;
            }
            if(i==n)
                printf("YES\n");
            else
                printf("NO\n");
            del(root);

        }
    }
    return 0;
}

hdu 1671 Phone List (字典树)

原文：http://blog.csdn.net/lp_opai/article/details/39159767