文章
9
粉丝
40
获赞
25
访问
1.8k
求助为何这样通过率为0,根据所有的字符串构造一棵Trie树,利用深度优先遍历寻找Trie树叶子节点的个数。由于示例“kdfa”是“kdfa”的前缀,故统计到叶子节点时,只有cnt[p]==1时才将该字符串统计进去,避免了相同字符串的统计。测试用例在本地ide中能够正确表示,求指教,本代码还有什么问题?
//Trie树
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int son[N][26],cnt[N],idx = 1;
int leafnum;
void insert(string str){
int p = 0;
for(int i = 0;str[i];i ++){
int c = str[i] - 'a';
if(!son[p][c]) son[p][c] = idx++;
p = son[p][c];
}
cnt[p]++;
}
void countleaf(int p){
bool flag = false;
for(int i = 0;i < 26;i ++){
if(son[p][i]) {
flag = true;
countleaf(son[p][i]);
}
}
if(!flag && cnt[p] == 1) leafnum ++;
}
int main(){
int n;
while(cin>>n){
if(n == 0) break;
leafnum = 0;
memset(son,0,sizeof(son));
memset(cnt,0,sizeof(cnt));
idx = 1;
string str;
while(n--){
...
登录后发布评论
题目好像没说是小写字母,也没说一定是字母,说的是字符