电话列表

题目 电话列表

思路分析

判前缀子串很明显trie树

在插入的时候就可以做判断

假设已经插入了 i个字符串，现在要插入一个字符串 str 那么此时 str产生不兼容的方式只有两种

str是前 i个已插入字符串的前缀

前 i个字符串中存在 str的前缀

对于第一种情况， str这个字符串在 trie中一定已经存在，所以一定不需要新开节点。如果开了新节点 就说明不满足1情况 所以用一个标记

对于第二种情况， 在插入 str时一定会遇到一个节点被标记为了终点 对于每一个点都判断是否是某个串的终点 如果存在 说明满足2情况

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=100010;

int son[N][10];

int idx;

bool exist[N];

char str[10010];

int n,T;

bool insert(char *str)

{

    int p=0;

    bool case_1=false;//是否新开结点 新开表示该串不是其他串的子串

    bool case_2=false;//路上是否遇到其他串的结束标记 遇到说明包含其他串

    for(int i=0;str[i];i++)

    {

        int u=str[i]-'0';

        if(!son[p][u]){

            son[p][u]=++idx;

            case_1=true;

        }

        p=son[p][u];

        if(exist[p])

            case_2=true;

    }

    exist[p]=true;

    return case_1 && !case_2;

}

int main()

{

    cin>>T;

    while(T--)

    {

        cin>>n;

        memset(son,0,sizeof son);

        memset(exist,false,sizeof exist);

        idx=0;

        bool res=true;

        for(int i=0;i<n;i++){

            cin>>str;

            if(!insert(str))

                res=false;

        }

        if(res)

            cout<<"YES"<<endl;

        else

            cout<<"NO"<<endl;

    }

    return 0;

}

同类题型

视频讲解

⬅️ 查询字符串 🏠 00-刷题理模型 ➡️ 字符串哈希