POJ3630-Phone List

Phone List

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 33437		Accepted: 9660

Description

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let's say the phone catalogue listed these numbers:

Emergency 911
Alice 97 625 999
Bob 91 12 54 26

In this case, it's not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob's phone number. So this list would not be consistent.

Input

The first line of input gives a single integer, 1 ≤ t ≤ 40, the number of test cases. Each test case starts 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 phone number 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

Sample Output

NO
YES

题目大意：是否存在某个号码是某个号码的前缀。

思路：①数据比较小，考虑暴力 ②字典树

①暴力代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
using namespace std;

int T, n;

bool cmp(string a, string b) {
	if(a[0] == b[0])
		if(a == b)
			return a.length() < b.length();
		else
			return a < b;
	else
		return a[0] < b[0];
}

string s[100010], temp;

int main() {
	scanf("%d", &T);
	while(T--) {
		scanf("%d", &n);
		for(int i = 0; i < n; i++) {
			cin >> temp;
			s[i] = temp;		
		}
		sort(s, s+n, cmp);//排序之后比较好比，但是复杂度上去了 
		
		int flag = 0;
		for(int i = 0; i < n-1; i++) {
				string temp = s[i+1].substr(0, s[i].length());//从是s[i+1]的0开始，取s[i]的长度，是否一样。 
				if(temp == s[i])
					flag = 1;
		}
		if(flag == 0) 
			printf("YES
");
		else
			printf("NO
");
	}
}

② a. 动态链表超时代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;

bool flag;

typedef struct Trie_Node{
	int num;
	bool isword;
	struct Trie_Node* next[10];
	Trie_Node() {//初始化 
		for(int i = 0; i < 10; i++)
			next[i] = NULL;
		num = 0;//到达该位置的字符串数量 
		isword = false;//单词结束 
	}
}trie;

void insert(trie* root, char* s) {
	trie* p = root;
	int i = 0;
	while(s[i] != '') {
		if(p->next[s[i]-'0'] == NULL) {//如果该位置为空，就开一个指向它 
			trie* temp = new trie();
			p->next[s[i]-'0'] = temp;
		} else {//之前某个单词结束了  或者是 自己结束了 
			if(p->next[s[i]-'0']->isword == true || s[i+1] == '') {
				flag = false;
				return;
			}
		}
		p = p->next[s[i]-'0'];//继续跑 
		i++;
		p->num++;//到达此处字符串+1 
	}
	p->isword = true;//单词结束 
}

void del(trie *root) {//删除 
	for(int i = 0; i < 10; i++) {
		if(root->next[i] != NULL) {
			del(root->next[i]);
		}
	}
	free(root);
}

int main() {
	int T, n;
	char s[20];
	scanf("%d", &T);
	while(T--) {
		trie* root = new trie();
		scanf("%d", &n);
		flag = true;//标志好用 
		for(int i = 0; i < n; i++) {
			scanf("%s", s);
			if(flag)
				insert(root, s);
		}
		if(flag)
			printf("YES
");
		else
			printf("NO
");
		del(root);//很重要 
	}
}

b.静态链表不会超时：（kuangbin）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;

bool flag;
int cnt;

typedef struct Trie_Node{
	struct Trie_Node *next[10];
	bool isword;
}trie;
trie memory[1000000];//直接开出来 和 动态没太大区别 

void init(trie **root) {//初始化，把root的地址 指向空 
	*root = NULL;
}

trie *creat() { //创建 
	trie *p;
	p = &memory[cnt++];//让p 指向 cnt（新的memory） 
	p->isword = false;//初始化 
	for(int i = 0; i < 10; i++) {
		p->next[i] = NULL;
	}
	return p;//返回指针 
}

void insert(trie **root, char *s) {
	trie *p;
	if(!(p = *root))//如果指向为空 就创建 （应该是第一个） 
		p = *root = creat();
	int i = 0;
	while(s[i]) {
		if(p->next[s[i]-'0']) {//如果该位置，已经是true 说明某个单词结束过了 或者是 自己结束了  
			if(p->next[s[i]-'0']->isword == true || s[i+1] == '') {
				flag = false;
				return;
			}
		} else p->next[s[i]-'0'] = creat();//为空，就创建 
		p = p->next[s[i]-'0'];
		i++;
	}
	p->isword = true;//单词结束 
}

int main() {
	char s[20];
	trie* root = NULL;
	int T;
	scanf("%d", &T);
	int n;
	while(T--) {
		flag = true;
		cnt = 0;
		scanf("%d", &n);
		init(&root); 
		for(int i = 0; i < n; i++) {
			scanf("%s", s);
			if(flag)
				insert(&root, s);//传的是根的地址，所以每次都是从根开始跑，然后插入的 （注意和引用区别开）  
		}
		if(flag)
			printf("YES
");
		else
			printf("NO
");
	}
}

感谢kuangbin神犇的指引，推荐博客：kuangbin

也可以使用数组模拟，推荐博客：数组模拟