hdu 1671 Phone List（字典树）题解

题意：给一连串数字，如果有前缀重复给出NO，否则给出YES

思路：这道题要delete否则爆内存，之前想的直接在insert（）里解决查询有错误，所以先保存数据再查询。

代码：

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<queue>

#include<cmath>

#include<string>

#include<stack>

#include<set>

#include<map>

#include<vector>

#include<iostream>

#include<algorithm>

#include<sstream>

#define ll long long

const int N=10005;

const int INF=1e9;

using namespace std;

char s[N][15];

struct Trie{

	int num;

	Trie *next[10];

	Trie(){

		num=0;

		for(int i=0;i<10;i++){

			next[i]=NULL;

		}

	}

};

Trie *root;

void insert(char s[]){

	int len=strlen(s);

	Trie *p=root;

	for(int i=0;i<len;i++){

		int v=s[i]-'0';

		if(p->next[v]==NULL){

			p->next[v]=new Trie();

		}

		p=p->next[v];

	}

	if(!p->num){

		p->num++;

	}

}

int query(char s[]){

	int len=strlen(s),v;

	Trie *p=root;

	for(int i=0;i<len;i++){

		v=s[i]-'0';

		p=p->next[v];

		if(p->num && i!=len-1) return 1;

	}

	return 0;

}

void del(Trie *p){

	if(p==NULL) return;

	for(int i=0;i<10;i++){

		if(p->next[i]!=NULL) del(p->next[i]);

	}

	delete p;

}

int main(){

	int flag,t,n;

	scanf("%d",&t);

	while(t--){

		root=new Trie();

		scanf("%d",&n);

		for(int i=0;i<n;i++){

			scanf("%s",s[i]);

			insert(s[i]);

		}

		flag=0;

		for(int i=0;i<n;i++){

			if(flag) break;

			flag=query(s[i]);

		}

		if(flag) printf("NO\n");

		else printf("YES\n");

		del(root);

	}

    return 0;

}