HDU 1671 Phone List (Trie·数组实现)

时间：2021-06-14 03:14:24

链接：http://blog.csdn.net/acvay/article/details/47089657

题意  给你一组电话号码  判断其中是否有某个电话是另一个电话的前缀

字典树的基础应用  可以先把所有电话存进Trie  标记每个电话的结束字符  然后再查询每个号码  看中途是否有结束标记  有的话就说明有号码是这个号码的前缀了

实际上  插入完成就能知道是否有号码是另一个号码的前缀了  假设A是B的前缀

若A在B之前插入  那么插入B的时候会遇到A的结束标记

弱A在B之后插入  那么A插入完成之后的结点还有非空的孩子结点

这样就只用在每次插入时判断就行了  可以省掉查询这一步

指针和动态内存分配实现字典更容易些  但在有多组样例的时侯不释放内存会导致MLE  释放内存又要多花费不必要的时间  可能导致TLE  所以用数组实现比较好

#include<cstdio>

#include<cstring>

using namespace std;

const int N = ;

char tel[N][];

int trie[N * ][], L;

bool end[N * ], flag;

void initTrie() {

    L = ;

    memset(trie, , sizeof(trie));

    memset(end, , sizeof(end));

}

void _insert(char *s) {

    int r = , i = , j;

    while (s[i]) {

        if (end[r]) flag = false;

        j = s[i++] - '';

        if (!trie[r][j])

            trie[r][j] = L++;

        r = trie[r][j];

    }

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

        if (trie[r][i]) flag = ;

        end[r] = ;

    }

}

int main() {

    int T, n;

    scanf("%d", &T);

    while (T--) {

        initTrie();

        scanf("%d", &n);

        flag = true;

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

            scanf("%s", tel[i]);

            _insert(tel[i]);

        }

        puts(flag ? "YES" : "NO");

    }

    return ;

}

相关文章