网站产品整合推广,山东交通学院精品课程建设网站,北京美陈设计制作公司,设计专业自学网站208. 实现 Trie (前缀树)
题目描述#xff1a;Trie#xff08;发音类似 “try”#xff09;或者说 前缀树 是一种树形数据结构#xff0c;用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景#xff0c;例如自动补完和拼写检查。
请你实现 Trie 类…208. 实现 Trie (前缀树)
题目描述Trie发音类似 “try”或者说 前缀树 是一种树形数据结构用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景例如自动补完和拼写检查。
请你实现 Trie 类 Trie() 初始化前缀树对象。 void insert(String word) 向前缀树中插入字符串 word 。 boolean search(String word) 如果字符串 word 在前缀树中返回 true即在检索之前已经插入否则返回 false 。 boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix 返回 true 否则返回 false 。
考察重点前缀查询树
方法概括利用struct{Trie[26];bool Endflag}存储录入的字符串并判断字符串是否存在或是否为前缀。
type Trie struct {Next []*Trie //这里需要存放指针数组而不是对象数组Endflag bool //如果是对象[]Trie则Insert中改变EndFlag不会起作用改变Next仍会起作用,因为数组存的是指针Endflag存的是对象
}/*输入ab的情况
root.Next a b c ... z root 指向 a|
a.Next a b c ... z root 指向 b,b.EndFlag true|
b.Next a b c ... z没有指向下一层的均为*Trie nil,即空指针*/
func Constructor2() Trie {return Trie{Next: make([]*Trie, 26), Endflag: false}
}func (trie *Trie) Insert(word string) {for i : 0; i len(word); i { //遍历字符串if trie.Next[word[i]-a] nil { //每一层会生成至多26*26个*Trie节点var temp Trie Constructor2()trie.Next[word[i]-a] temp}trie trie.Next[word[i]-a]//Trie跟随字符串进行树的生成 trie创建trie.Next[0]trie指向trie.Next[0]即a-a-p-pEndFlagtrue}trie.Endflag true
}func (trie *Trie) Search(word string) bool {for i : 0; i len(word); i {if trie.Next[word[i]-a] nil { //遍历不完字符串说明没有该字符串return false}trie trie.Next[word[i]-a]}return trie.Endflag //遍历完成字符串判断是否为终点如果是存放的是apple则app虽然可以遍历完但依旧返回false
}func (trie *Trie) StartsWith(prefix string) bool {for i : 0; i len(prefix); i {if trie.Next[prefix[i]-a] nil { //前缀字符串只要可以遍历完都返回truereturn false}trie trie.Next[prefix[i]-a]}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);*/
