Phone List

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

NO
YES

解题思路：

建立字典树。关键是设立某个串结尾的标志，即在哪个字母结尾。要推断是否存在前缀要考虑两种情况。一是当前输入的串是否是曾经输入的串的前缀，而是曾经输入的串是否是当前输入的串的前缀。前一种情况在查找该串时，会从第一个字母查找到最后一个字母，中间不返回不论什么值，说明当前的串是曾经的前缀。后一种情况，当在查找当前串的时候遇到曾经串结束的标志。则说明曾经串是当前串的前缀。代码中结束的标志为保存串中最后一个字母的那个节点的cnt值为-1.

如图：

代码：

#include <iostream>
#include <malloc.h>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;
const int maxn=10;
bool ok;
char str[12];
int t,n;

struct Trie
{
    int cnt;
    Trie *next[maxn];
};

Trie *root;

void CreateTrie(char *str)
{
    int len=strlen(str);
    Trie*p=root,*q;
    for(int i=0;i<len;i++)
    {
        int id = str[i]-'0';
        if(p->next[id] == NULL)
        {
            q = (Trie *)malloc(sizeof(Trie));
            q->cnt = 1;
            for(int j=0; j<maxn; ++j)
                q->next[j] = NULL;
            p->next[id] = q;
            p = p->next[id];
        }
        else
        {
            p = p->next[id];
        }
    }
    p->cnt=-1;//串末尾的标志
}

int findTrie(char *str)
{
    int len=strlen(str);
    Trie *p=root;
    for(int i=0;i<len;i++)
    {
        int id=str[i]-'0';
        if(p->next[id]==NULL)
            return 0;//没有建过树
        if(p->next[id]->cnt==-1)
            return -1;//曾经串是当前串的前缀
        p=p->next[id];
    }
    return -1;//当前串是曾经串的前缀
}

void release(Trie *root)//释放空间
{
    for(int i=0;i<maxn;i++)
    {
        if(root->next[i])
            release(root->next[i]);
    }
    free(root);
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        ok=1;
        root=(Trie*)malloc(sizeof(Trie));//root为指针类型，须要申请空间
        for(int i=0; i<10; ++i)
            root->next[i] = NULL;
        scanf("%d",&n);
        while(n--)
        {
            scanf("%s",str);
            if(findTrie(str)==-1)
                ok=0;//有前缀
            if(!ok)
                continue;//有前缀。后面的就不用建树了
            CreateTrie(str);
        }
        if(ok)
            printf("YES\n");
        else
            printf("NO\n");
        release(root);
    }
    return 0;
}