题目链接
题目描述
有n个电话号码，长度对多为10个，问存不存在一个电话号码是另一个的前缀，是就输出NO，否则YES。 1. n<
思路
Trie树裸题 1. 把所有字符串插入Trie树 2. 插入时进行以下判断： a. 当前插入的字符串可以沿着Tries树中的某条路径一直往下走，，不用新开节点：可能比这条路径表示的字符串长，即最后才新开节点。可能比它短，即当前插入字符串读完后，Tries树的这条路径还可延伸。 b. Trie树的这条路径没走完就新开节点，显然就不是前缀
代码;int ch[100000+10][10+1];int sz;bool insert(char *s){bool flag = false;int j,n;int u = 0;n = strlen(s);for(int i = 0; i<n; i++){int c = s[i] – ‘0’;if(!flag && u){for(j = 0; j<10; j++)if(ch[u][j] != -1) break;if(j == 10) return true;}if(ch[u][c] == -1){memset(ch[sz], -1, sizeof(ch[sz]));ch[u][c] = sz++;flag = true;}u = ch[u][c];}if(!flag) return true;return false;}int main(){int cas;scanf(“%d”,&cas);while(cas–){int n, i;scanf(“%d”,&n);sz = 1;memset(ch[0], -1, sizeof(ch[0]));bool flag = false;for(i = 0; i<n; i++){char s[10+5];scanf(“%s”,s);if(flag) continue;flag = insert(s);}if(!flag) printf(“YES\n”);elseprintf(“NO\n”);}return 0;}
不义而富且贵，于我如浮云。
