Golang实现Trie(前缀树)的示例
定义
前缀树是N叉树的一种特殊形式。通常来说，一个前缀树是用来存储字符串的。前缀树的每一个节点代表一个字符串（前缀）。每一个节点会有多个子节点，通往不同子节点的路径上有着不同的字符。子节点代表的字符串是由节点本身的原始字符串，以及通往该子节点路径上所有的字符组成的。
下面是前缀树的一个例子：
在上图示例中，我们在节点中标记的值是该节点对应表示的字符串。例如，我们从根节点开始，选择第二条路径 ‘b’，然后选择它的第一个子节点 ‘a’，接下来继续选择子节点 ‘d’，我们最终会到达叶节点 “bad”。节点的值是由从根节点开始，与其经过的路径中的字符按顺序形成的。
值得注意的是，根节点表示空字符串。
前缀树的一个重要的特性是，节点所有的后代都与该节点相关的字符串有着共同的前缀。这就是前缀树名称的由来。
我们再来看这个例子。例如，以节点 “b” 为根的子树中的节点表示的字符串，都具有共同的前缀 “b”。反之亦然，具有公共前缀 “b” 的字符串，全部位于以 “b” 为根的子树中，并且具有不同前缀的字符串来自不同的分支。
前缀树有着广泛的应用，例如自动补全，拼写检查等等。我们将在后面的章节中介绍实际应用场景。
问题描述
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。
实现思路：
由于所有输入都是小写字母构成，可以用桶的方式实现，虽然有空间浪费，但是速度最快。
同时要实现搜索词和搜索词前缀。考虑加入布尔标识是否是一个词。但插入词的时候，到词的最后一个字母时，将该节点布尔设为true 代码：
type Trie struct {
isWord bool
children [26]*Trie
}
func Constructor() Trie {
return Trie{}
}
func (this *Trie) Insert(word string) {
cur := this
for i, c := range word {
n := c - 'a'
if cur.children[n] == nil {
cur.children[n] = &Trie{}
}
cur = cur.children[n]
if i == len(word)-1 {
cur.isWord = true
}
}
}
func (this *Trie) Search(word string) bool {
cur := this
for _, c := range word {
n := c - 'a'
if cur.children[n] == nil {
return false
}
cur = cur.children[n]
}
return cur.isWord
}
func (this *Trie) StartsWith(prefix string) bool {
cur := this
for _, c := range prefix {
n := c - 'a'
if cur.children[n] == nil {
return false
}
cur = cur.children[n]
}
return true
}
到此这篇关于Golang实现Trie(前缀树)的示例的文章就介绍到这了,更多相关Golang 前缀树内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
