HDU1305Immediate Decodability(字典树)
题目链接:hdu1305
题目大意:给一大堆01串,并以9表示一组01串输入结束,问这些串之间是否至少有一个串是另一个串的前缀。
解题思路:毫无疑问,可以用Trie来维护这些串,每次插入时判断是否含有当前串str的前缀串或者自己是别的串的前缀串,代码种的查询时query2。查询的复杂度O(n)。
字典树介绍
字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,...
原创
2019-02-05 21:37:38 ·
253 阅读 ·
0 评论