Trie树 应用 Phone List

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

NO
YES

     针对这一题来分析：

           题 意：给n个串,看是否有一个串是另一个串的前缀。因为数据量相对来讲比较大，如果用两两比较，会TL,所以 O(n^2)显然过不了这题。  字典树却很容易处理，但是这里在实现的时候 就有问题了，设置节点信息包括flag标志是否到达一个单词尾部，另外设置一个数组记录此结点的儿子结点的数组下标。在插入过程中就可以进行查询。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX 10

typedef struct TrieNode{
	bool isPhone;
	TrieNode *next[MAX];
	void initialTrie(){
		isPhone = false;
		for(int i = 0 ; i < MAX ; i++){
			next[i] = NULL;
		}
	}
}TrieNode;

bool isPrefixPhone = false;



void addWord(TrieNode *node,char *ch){
	if(node == NULL || *ch == '\0')
		return;
	TrieNode *p = node;
	int i,len;
	for(i = 0 ; i < (len=strlen(ch)) ; i ++){
		if(p->next[ch[i]-'0'] == NULL){
			TrieNode *tmp = (TrieNode*)malloc(sizeof(TrieNode));
			//初始化以temp为顶点节点的子树
			tmp->initialTrie();
			p->next[ch[i]-'0'] = tmp;	
		}else{		
			if(p->next[ch[i]-'0']->isPhone && i <= len - 1){
				isPrefixPhone = true;
				return;
			}
		}
		p = p->next[ch[i]-'0'];
	}
	p->isPhone = true;
	//如果先输入12，再输入1，那么就需要下面的代码进行判断
	for(i = 0 ; i < MAX ; i ++){
		if(p->next[i] != NULL){
			isPrefixPhone = true;
			return;
		}
	}
}


void delTree(TrieNode *root){
	for(int i = 0 ; i < MAX ; i ++){
		if(root->next[i] != NULL){
			delTree(root->next[i]);
		}
		delete root->next[i];
	}
}



int main(){
	int t,n,i;
	char s[11];
	scanf("%d",&t);
	TrieNode *root = (TrieNode*)malloc(sizeof(TrieNode));
	while(t--){	
		root->initialTrie();
		isPrefixPhone = false;
		scanf("%d",&n);
		for(i = 0 ; i < n ; i ++){
			scanf("%s",s);
			if(isPrefixPhone) continue;
			addWord(root,s);
		}
		printf(isPrefixPhone ? "NO\n":"YES\n");
		delTree(root);
	}
	return 0;
}

    网上大牛写的静态版

    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int MAXNODE=500000;
    const int BRANCH=10;

    int Tree[MAXNODE][BRANCH],SIZE;
    bool Key[MAXNODE];
    bool Insert(char *str) {
        int Node=0;bool tof=false;
        for (int i=0;str[i];i++){
            int c=str[i]-'0';
            if(Tree[Node][c]==-1){
                Tree[Node][c]=++SIZE;tof=true;
                memset(Tree[SIZE],-1,sizeof(Tree[SIZE]));
            }
            if(Key[Node]) return false;
            Node=Tree[Node][c];
        }
        Key[Node]=true;
        return tof;
    }

    void Trie(){
        memset(Tree[0],-1,sizeof(Tree[0]));
        SIZE=0;
    }

    char str[15];
    int main()
    {
        int t,n;bool tof;
        scanf("%d",&t);
        while(t--){
            memset(Key,false,sizeof(Key));
            Trie();tof=true;
            scanf("%d",&n);
            for(int i=0;i<n;i++){
                scanf("%s",str);
                if(tof){
                    tof=Insert(str);
                }
            }
            if(tof) puts("YES");
            else puts("NO");
        }
    }