HDU-1671-Phone List

最新推荐文章于 2019-04-01 18:13:04 发布

Cambridge

最新推荐文章于 2019-04-01 18:13:04 发布

阅读量1k

点赞数 1

分类专栏： ACM_HDU 文章标签： null insert delete struct list

本文链接：https://blog.csdn.net/Cambridgeacm/article/details/7840560

版权

ACM_HDU 专栏收录该内容

28 篇文章

订阅专栏

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 10005
char 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;
}