swift's blog

swift's blog

题解 UVA11362 【Phone List】

posted on 2019-09-01 19:28:17 | under 题解 |

一道很简单的字典树模版题

字典树是什么?

简单的说,字典树就是把很多个字符串合并在一起,如下图一样的树,详细建立的方法可以看我的代码 https://s2.ax1x.com/2019/06/15/VIwGuR.png

我们把所有的电话号码建成一颗字典书,在插入的过程住如果发现有结束标记,或者结束时发现这个节点还有儿子,就输出$NO$,如果没有发现这种情况就输出$YES$

代码:

#include<bits/stdc++.h>
using namespace std;
int cnt;
struct trie{
    int son[10],end=0;
}a[1000001];
int main(){
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        memset(a,0,sizeof(a));
        int n;
        cnt=0;
        scanf("%d",&n);
        bool flag=0;
        for(int j=1;j<=n;j++){
            string s;
            cin>>s;
            int now=0;
            for(int k=1;k<=s.length();k++){
                if(a[now].son[s[k-1]-'0']){
                now=a[now].son[s[k-1]-'0']; 
                }
                else{
                a[now].son[s[k-1]-'0']=++cnt;
                now=cnt;
                }
                if(a[now].end==1){
                    flag=1;
                }
                if(k==s.length()){
                    for(int i=0;i<=9;i++){
                        if(a[now].son[i])flag=1;
                    }
                    a[now].end=1;
                }
            }
        }
        if(flag){
            puts("NO");
        }
        else{
        puts("YES");
        }
    }
    return 0;
}