Phone List HDU - 1671(字典树）

﹏ヽ暗。殇╰゛Y 2023-08-17 15:41 133阅读 0赞

# Phone List HDU - 1671 #

题目链接：[https://vjudge.net/problem/HDU-1671][https_vjudge.net_problem_HDU-1671]

题目：

给出一个电话号码列表，确定它是否一致，因为没有数字是另一个号码的前缀。 假设电话目录列出了这些数字：  
 1. Emergency 911  
2. Alice 97 625 999  
3. Bob 91 12 54 26  
     在这种情况下，无法呼叫Bob，因为只要您拨打了Bob的电话号码的前三位数字，中心就会将您的呼叫转接到紧急线路。 所以这个列表不一致。  
输入  
     第一行输入给出一个整数，1 <= t <= 40，即测试用例的数量。 每个测试用例以n（电话号码的数量）在单独的行上开始，1 <= n <= 10000.然后是n行，每行有一个唯一的电话号码。 电话号码是最多十位数的序列。  
产量  
     对于每个测试用例，如果列表一致则输出“YES”，否则输出“NO”。

**思路：将这些电话号码插入字典树中，只要出现一个电话号码是另一个电话号码的前缀，那么就输出“NO”否则输出“YES”，**

**这题要注意内存的控制，否则会MLE，还有不能n方来利用find前缀函数判断每一个字符串在其他字符串是否是前缀，否则会TLE，**

**只要在将电话号码插入字典树的时候判断p->num是否不为0即可，如果不为0就break，很好的避免了n方判断、**

// 
    // Created by HJYL on 2019/8/20.
    //
    #include <iostream>
    #include <vector>
    #include <map>
    #include <string>
    #include <queue>
    #include <stack>
    #include <set>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstdlib>
    using namespace std;
    typedef long long ll;
    const int maxn=1e6+10;
    struct trie{
        int sum;
        trie* next[10];
    }*root;
    trie* build()
    {
        trie *T=(trie *)malloc(sizeof(trie));
        T->sum=0;
        for(int i=0;i<10;i++)
            T->next[i]=NULL;
        return T;
    }
    bool flag;
    void insert(char* s)
    {
        trie* p=root;
        for(int i=0;s[i];i++)
        {
            if(p->next[s[i]-'0']==NULL)
            {
                p->next[s[i]-'0']=build();
            }
            p=p->next[s[i]-'0'];
            if(p->sum!=0)
            {
                flag=false;//一旦出现前缀就跳出
                break;
            }
        }
        p->sum++;//在字符串结尾，单词个数加一
        for(int i=0;i<10;i++)
        {
            if(p->next[i]!=NULL)
            {
                flag=false;
                return;
            }
        }
    }
    int find(char* s)
    {
        trie* p=root;
        for(int i=0;s[i];i++)
        {
            if(p->next[s[i]-'0']==NULL)
                return 0;
            else
                p=p->next[s[i]-'0'];
        }
        return p->sum;
    }
    void delte(trie *p)//很最重要的内存删除
    {
    
        if(p!=NULL) {
            for(int i = 0; i < 10; i++) {
                if(p->next[i]!=NULL)
                    delte(p->next[i]);
            }
        }
        free(p);
        p=NULL;
    }
    int main()
    {
        //freopen("C:\\Users\\asus567767\\CLionProjects\\untitled\\text", "r", stdin);
        int T,n;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&n);
            root=build();
            char str[10007][50];
            flag=true;
            for(int i=0;i<n;i++)
            {
                scanf("%s",str[i]);
                insert(str[i]);
            }
            if(flag)
            {
                printf("YES\n");
                delte(root);
            } else
            {
                printf("NO\n");
                delte(root);
            }
    
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11386356.html

[https_vjudge.net_problem_HDU-1671]: https://vjudge.net/problem/HDU-1671