前缀树是处理字符串常见的数据结构。
前缀树一般包含四个功能:1.添加word void insert(string word)
2. 删除word void delete(string word)
3. 查询是否在字典树中 bool search(string word)
4.返回以字符串pre为前缀的单词数量 int prefixNumber(string pre):
哈希表:只能查一个字符串加入过几次,但查不了以“pre”某个开头,或者叫“前缀”的字符串有几个。前缀树可以查。
结构:1.如果字符是 a-z 26个字母的话,用数组结构比较好。也可以理解为,如果是数字,是10叉树,字母26叉树。
2.如果字符种类比较多,用哈希表比较好。
//26个字母
const int MaxNum = 26;
// 数组方式
class TrieNodeArr{
public:
int pass;
int end;
TrieNodeArr* nexts[MaxNum];//此处为指向下一个Node的指针
TrieNodeArr()
{
pass = 0;
end = 0;
for (int i = 0; i < MaxNum; i++)//是否需要new?
{
nexts[i] = NULL;
}
//如果字符全是小写 nexts 下级对应的路的位置 a-z 26个字母
//0-a ...25-z
//nexts[0]==NULL;表示没有走向a的路。
//nexts[0]!=NULL;表示有走向a的路。
//...
}
};
原文链接: https://www.cnblogs.com/jasmineTang/p/14369288.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/327909
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!