本文主要是介绍hdu 1671 Phone List（字典树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：点击打开链接
分析：两种思路，一是直接套字典树的模板（每个号码都存入字典树，边存边找，对于当前电话号码，因为长度随机，所以有可能是前面电话号的前缀（如之前9112，当前911），或者前面有电话是它的前缀（如之前911，当前9112），这时候就要判断。所以将每个电话号码的结尾标记，如果遍历当前字符串未完成的时候出现了前面字符串的结尾，说明之前有电话号是当前号码的前缀，如果遍历完当前电话号码之后，字典树下一层还有任何一个结点不为空，说明曾经有一个电话号码是以当前电话号码为前缀的。），二是将所有字符串按字典序排序，然后判断相邻的两个号码是否符合条件即可。证明见：点击打开链接
代码：
///思路一
///#include<bits/stdc++.h>///hdu不支持此头文件！！！
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 1e5;
struct trie{int next[10];int val;
}tree[5*maxn];
int cnt=1;
int flag=0;int init(){memset(&tree[cnt],0,sizeof(trie));return cnt++;
}void build(string s){int f=1;int tmp=0,len=s.size();for(int i=0;i<len;i++){int num=s[i]-'0';if(!tree[tmp].next[num]){tree[tmp].next[num]=init();f=0;}tmp=tree[tmp].next[num];if(tree[tmp].val&&(i!=len-1)) flag=1;///对应123 1234}tree[tmp].val++;if(f&&tmp)///对应 1234 123flag=1;
}int main(){///memset(&tree[0],0,sizeof(trie));int t,m;string a;cin>>t;while(t--){memset(tree,0,sizeof(tree));cin>>m;for(int i=0;i<m;i++)///不能在此数据输入处直接判断flag，然后break，这样会被认为有两组数据！！！cin>>a,build(a);if(flag) cout<<"NO"<<endl;else cout<<"YES"<<endl;flag=0;cnt=1;///注意重新赋初始值，debug了一天，唉，一直说是数组越界，经常忘记循环后赋初值，以后要吸取教训了，慎用全局变量。！！！///如果使用指针也要清空字典树，防止内存超限。}
}
///思路二
#include<algorithm>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const int maxn = 1e4+10;struct node{char str[12];bool operator <(const node &a)const///重载运算符{return strcmp(str,a.str)<0;}
}ph[maxn];int main(){int t,n;cin>>t;while(t--){int flag=0;cin>>n;for(int i=0;i<n;i++)cin>>ph[i].str;sort(ph,ph+n);char s1[12],s2[12];for(int i=0;i<n-1;i++){int l=min(strlen(ph[i].str),strlen(ph[i+1].str));strncpy(s1,ph[i].str,l),s1[l]='\0';///基本所有的字符串都已'\0'为结束标志，有的系统为自动加，为了防止错误，最好自己加'\0'！！！strncpy(s2,ph[i+1].str,l),s2[l]='\0';if(!strcmp(s1,s2)) {flag=1;break;}}/*或者利用strstr函数strstr(str1,str2) 函数用于判断字符串str2是否是str1的子串。如果是，则该函数返回str2在str1中首次出现的地址；否则，返回NULL。for(int i=0;i<n-1;i++){if(strstr(ph[i+1].str,ph[i].str)!=NULL){flag=1,break;}}*/for(int i=0;i<n;i++)cout<<ph[i].str<<" "<<endl;if(flag) cout<<"NO"<<endl;else cout<<"YES"<<endl;}
}
这篇关于hdu 1671 Phone List（字典树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
