本文主要是介绍hdu 1671 Phone List 字典树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// hdu 1671 Phone List 字典树
//
// 题目大意：
//
// 有一些电话号码的字符串长度最多是10，问是否存在字符串是其他字符串的前缀
//
//
// 解题思路：
//
// 字典树，先插入第一个字符串，然后按照查询，插入的方式进行访问，发现了之后
// 就不用再进行字典树的操作了
//
//
// 感悟：
//
// 题目意思很清楚，我在细节方面思考了很久，插入方面在每个串的根节点的时候加
// 上一个val值标记，查询的时候先看是否有标记，有则直接返回true，没找到返回
// false，找到了返回true就行了，还是很容易的~COME ON ! FIGHTING~#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>using namespace std;const int MAX_N = 300000;int n;struct Trie {int ch[MAX_N][11];int sz;int val[MAX_N];int idx(char c){return c - '0';}void init(){sz = 1;memset(ch[0],0,sizeof(ch[0]));val[0] = 0;}void insert(char *s,int v){int n = strlen(s);int u = 0;for (int i=0;i<n;i++){int c = idx(s[i]);if (!ch[u][c]){memset(ch[sz],0,sizeof(ch[sz]));val[sz] = 0;ch[u][c] = sz++;}u = ch[u][c];}val[u] = v;}bool query(char *s){int n = strlen(s);int u = 0;for (int i=0;i<n;i++){int c = idx(s[i]);//cout << s[i];if (val[u]){return true;}if (!ch[u][c]){return false;}u = ch[u][c];}return true;}}trie;void input(){trie.init();scanf("%d",&n);char s[20];scanf("%s",s);trie.insert(s,1);bool flag = false;for (int i=2;i<=n;i++){scanf("%s",s);if (flag)continue;flag = trie.query(s);//cout << endl;trie.insert(s,i);//cout << i << endl;}if (flag)puts("NO");elseputs("YES");
}int main(){int t;//freopen("1.txt","r",stdin);scanf("%d",&t);while(t--){input();}
}
这篇关于hdu 1671 Phone List 字典树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
