HDU 1671

//二维数组+动态内存+释放，需要注意指针数组的使用方法 
//和树完全建完后，怎么释放树 
//大致题意：多组电话号码，如果存在某组是其他组的前缀则输出NO 
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstring>
#include <cstdio> 
using namespace std;
char *str[10001];
typedef struct Node 
{
    int cnt ; 
    Node *child[11];
}Node;
void init(Node *root)
{
    int i;
    for(i=0;i<11;i++)
        root->child[i] = NULL;
    root->cnt=0;
}
void insert(char *s,Node *root)//注意指针数组的传参方式 
{
    Node *current = root;
    int i;
    for(i=0;i<s[i]!='\0';i++)
    {
        int index = s[i]-'0';
        if(current->child[index] != NULL)
        {
            current = current->child[index];
            (current->cnt)++;
        }
        else
        {
            Node *newnode = new Node;
            init(newnode);
            current->child[index] = newnode;
            current = newnode;
            current->cnt =1;
        }
    }
}
bool find (char *s,Node *root)
{
    Node *current = root;
    int i;
    /*
    for(i=0;s[i]!='\0';i++)
    {
        int index = s[i]- '0';
        if(current->child[index]&&current->cnt>1)
            current = current->child[index];
        //实际上下面这种情况不可能存在，但为保险起见，
        //没有直接else 
        //else if(current->child[index]==NULL)
          //  return true;
        else if(current->cnt=1)
            return false;
    }
    return true;
    */
    for(i=0;s[i]!='\0';i++)
    {
        int index = s[i]- '0';
        //不必再加上if判断了，必定可以走到末尾，因为他就是树里的串 
        current = current->child[index];
    }
    if(current->cnt==1) return false;
    return true;
}                                         
void My_delete(Node *root)
{
    int i;
    if(root==NULL)
        return ;
    else//加不加else均可ＡＣ 
    {
        for(i=0;i<11;i++)
        {
            if(root->child[i])
                My_delete(root->child[i]);
        }
    }
    delete root;
    return ;
}                      
int main()
{
    int i,j,k,T;
    cin>>T;
    while(T--)
    {
        Node *root = new Node;
        init(root);//开在局部,希望对减小内存有所帮助 
        int num;
        cin>>num;
        memset(str,0,sizeof(str));
        i=0;       
        k = num;
        while(num--)
        {
            //用指针数组的话，必须给他申请空间，否则出现内存不可写 
            str[i]=(char *)malloc(11*sizeof(char));
            cin>>str[i];
            //gets(str[i]);
            /*
            刚开始这用的是gets，上面cin>>num时，
            没有吸收掉换行符会被gets吸收，所以输入少于一行时就输出了结果 
            换位cin以后就不必加上getchar了，因为cin不接受换行符
            */ 
            insert(str[i],root);
            i++;
        }
        //上面的num已经变化，所以下面不可再使用num（num=-1） ,看来以后在内部输入还是用for循环吧 
        for(j=0;j<k;j++)
        {
            bool flag = find (str[j],root);
            if(flag)
            {
                cout<<"NO"<<endl;
                break;
            }
        }
        if(j==k)
            cout<<"YES"<<endl;
        My_delete(root);
    }
    return 0;
}