Phone List

Time Limit: 3000/1000 MS (Java/Others) Memory Limit:32768/32768 K (Java/Others)
Total Submission(s): 4602 Accepted Submission(s): 1557

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1671

Problem Description

Given a list of phone numbers,determine if it is consistent in the sense that no number is the prefix ofanother. Let’s say the phone catalogue listed these numbers:
1. Emergency 911
2. Alice 97 625 999
3. Bob 91 12 54 26
In this case, it’s not possible to call Bob, because the central would directyour call to the emergency line as soon as you had dialled the first threedigits of Bob’s phone number. So this list would not be consistent.

 

Input

The first line of input givesa single integer, 1 <= t <= 40, the number of test cases. Each test casestarts with n, the number of phone numbers, on a separate line, 1 <= n <=10000. Then follows n lines with one unique phone number on each line. A phonenumber is a sequence of at most ten digits.

 

Output

For each test case, output“YES” if the list is consistent, or “NO” otherwise.

 

Sample Input

2

3

911

97625999

91125426

5

113

12340

123440

12345

98346

 

Sample Output

NO

YES

 

Source

2008 “Insigma International Cup” Zhejiang CollegiateProgramming Contest - Warm Up（3）

 

Recommend

lcy

 

题目大意：

         输入n个测试用例，m个字符串，判断是否存在某个字符串是否是另外一个字符串的子串，存在输出YES，不存在输出NO

解题思路：

         这是一个字典树的题目，首先建立字典树，边建立边判断，在一下情况返回false

1、  当前字符是最后一个字符，并且已经存在于字典树中

2、  当前字符不是这个字符串的最后一个字符，但是是另外一个字符传的最后一个字符

否则返回true

这个题目如果直接这样判断不释放上一次建树所用的内存的话要超时，所以每一个测试用例完之后要释放内存。

代码：

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 9
using namespace std;
struct Trie
{
    Trie *next[maxn];
    bool Islast;//判断这个字符是否是某个单词的结尾
};


//把字符串插入字典树root中
bool build(Trie *root,char *str)
{
    Trie *p=root;
    Trie *q;
    int len=strlen(str);
    for(int i=0;i<len;i++)
    {
        int id=str[i]-'0';
        if(p->next[id]!=NULL)
        {
			if(i==len-1)
			{//到最后一个数依然存在相同的数字
				return false;
			}
			//已经有单词在这里结尾
			if(p->next[id]->Islast==true)
				return false;
            p=p->next[id];			
            continue ;
        }
        //没有该节点
        q=(Trie *)malloc(sizeof(Trie));
        for(int j=0;j<=maxn;j++)
        {
            q->next[j]=NULL;
        }

		
		if(i==len-1)
		{
			q->Islast=true;
		}
		if(q->Islast==true)
		{
			p->next[id]=q;
			p=p->next[id];
			continue;
		}
		else 
		{
			
			q->Islast=false;
			p->next[id]=q;
			p=p->next[id];
		}
		
    }
	return true;
}

//释放内存
int dealTrie(Trie* T)
{
    int i;
    if(T==NULL)
        return 0;
    for(i=0;i<maxn;i++)
{
//释放每一个节点的内存
        if(T->next[i]!=NULL)
            dealTrie(T->next[i]);
    }
    free(T);
    return 0;
}

int main()
{
	int tc;
	int n;
	Trie *root;
	char ch[30];
	bool flag;
	scanf("%d",&tc);
	while(tc--)
	{
		flag=true;
		root=(Trie *)malloc(sizeof(Trie));
		for(int j=0;j<=maxn;j++)
		{
			root->next[j]=NULL;
		}
		scanf("%d",&n);
		getchar();
		while(n--)
		{
			
			gets(ch);
			if(build(root,ch)==false)
			{
				flag=false;
			}
		}
		if(flag)
			printf("YES\n");
		else
			printf("NO\n");
		dealTrie(root);//释放内存空间，要一个一个节点释放，不能用free(root);
	}
    

    return 0;
}