大家好，欢迎来到IT知识分享网。
先扫盲：前缀树一般指 字典树 Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它有3个基本性质：
根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。
想深入了解可移步百度百科。
题目：
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。示例:
说明:
- 你可以假设所有的输入都是由小写字母 a-z 构成的。
- 保证所有输入均为非空字符串。
解题思路：使用bool表示当前字符是否是某一字符串的尾部。
type Trie struct {
isTail bool
next [26]*Trie
}
/ Initialize your data structure here. */
func Constructor() Trie {
return Trie{}
}
/ Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
p:=this
for i:=0;i<len(word);i++{
k:=word[i]-‘a’
if p.next[k]==nil{
trie:=Constructor()
p.next[k]=&trie
}
p=p.next[k]
}
p.isTail = true
/ Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
p:=this
for i:=0;i<len(word);i++{
k:=word[i]-‘a’
if p.next[k]!=nil{
p=p.next[k]
}else{
return false
}
}
return p.isTail
}
/ Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
p:=this
for i:=0;i<len(prefix);i++{
k:=prefix[i]-‘a’
if p.next[k]!=nil{
p=p.next[k]
}else{
return false
}
}
return true
}
/
* Your Trie object will be instantiated and called as such:
* obj := Constructor();
* obj.Insert(word);
* param_2 := obj.Search(word);
* param_3 := obj.StartsWith(prefix);
*/
执行用时：72 ms
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/175591.html
