trie树,又称单词查找树,前缀树,字典树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计,自动补全等。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
看下trie树大概长什么样
其实就是一种简单的数据结构。
下面从题目开始入手。
思路:用结构体表示节点,is_end表示是否是单词的结尾,child数组表示后继节点
1 | class Trie { |
trie树,又称单词查找树,前缀树,字典树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计,自动补全等。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
看下trie树大概长什么样
其实就是一种简单的数据结构。
下面从题目开始入手。
思路:用结构体表示节点,is_end表示是否是单词的结尾,child数组表示后继节点
1 | class Trie { |