HDU-1671-Phone List

HDU-1671-Phone List

http://acm.hdu.edu.cn/showproblem.php?pid=1671

字典树，判断是否有某个数字是另一个数字的前缀，注意123不是123的前缀，建树之后要删除节点，否则会Memory LimitExceeded

写的比较麻烦，分两种情况，一是先出现123，再出现1234,；二是先出现1234，再出现123

#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>using namespace std;#define N 10005char str[N];struct node{	int count;	node *childs[10];	node()	{		count=0;		int i;		for(i=0;i<=9;i++)		childs[i]=NULL;	}};node *root,*current,*newnode;int flag;void del(node *head)  {	int i;	for(i=0;i<=9;i++)	if(head->childs[i]!=NULL)	del(head->childs[i]);	delete(head);}int judge(node *head){	int i;	for(i=0;i<=9;i++)	if(head->childs[i]!=NULL)	return 1;	return 0;}void insert(char *str){	int i,m;	current=root;	for(i=0;i<strlen(str);i++)	{		m=str[i]-'0';		if(current->childs[m]!=NULL)		{			current=current->childs[m];			if((i<strlen(str)-1&¤t->count==1)||(i==strlen(str)-1&&judge(current)))  			{				flag=1;				break;			}		}		else		{			newnode=new node;			current->childs[m]=newnode;			current=newnode;		}	}	current->count=1;}int main(){	int t,i,n;	scanf("%d",&t);	while(t--)	{		scanf("%d",&n);		flag=0;		root=new node;		while(n--)		{			scanf("%s",str);			if(flag==1)			continue;			insert(str);		}		if(flag)		printf("NO\n");		else		printf("YES\n");		del(root);	}	return 0;}