题解 SP4033 【PHONELST - Phone List】

Lalenture · 2018-08-13 19:46:30 · 题解

include <bits/stdc++.h>

define N 400010

using namespace std;

int T,n,ch[N][11],tot,pre[N],ove[N];//数字只有十个顾第二维开到11

bool bo[N],flag;

char s[20];

void insert(char *s) {

int len = strlen(s);//字符串的长度
int u = 1;//根节点
for(int i = 0; i < len ; i++) 
{
    int c = s[i] - '0';
    if(!ch[u][c])//如果这个数字不在字典树内，就加入
    {
        ch[u][c] = ++tot;
    }
    u = ch[u][c];//更新节点
    pre[u]++;
    if(ove[u])  {flag = 1 ;return;}
    if(bo[u])   flag = true;//经过某跟被标记的节点 
}
ove[u] = 1;
if(pre[u] > 1)
{
    flag = true;
    return;
}

}

int main() {

scanf("%d",&T);
while(T--)
{
    scanf("%d",&n);
    tot = 1;
    flag = false;
    memset(ch,0,sizeof(ch));
    memset(pre,0,sizeof(pre));
    memset(ove,0,sizeof(ove));
    bool ans = false;
    for(int i = 1; i <= n ;i++) 
    {
        scanf("%s",s);
        if(flag == false)
        insert(s);
    }
    if(flag)    puts("NO");
    else puts("YES");
} 
return 0;

}