亲宝软件园·资讯

展开

Golang实现Trie(前缀树)的示例

terrygmx 人气:0

定义

前缀树是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
}

/** Initialize your data structure here. */
func Constructor() Trie {
	return Trie{}
}

/** Inserts a word into the 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
		}

	}
}

/** Returns if the word is in the trie. */
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
}

/** Returns if there is any word in the trie that starts with the given prefix. */
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
}

/**
 * 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);
 */

加载全部内容

相关教程
猜你喜欢
用户评论