Leetcode-208. 实现Trie（前缀树）
前缀树是一个由“路径”和“节点”组成多叉树结构。由根节点出发，按照存储字符串的每个字符，创建对应字符路径，以此实现快速查找单词或是否为前缀的功能。
此题要求简单，只需实现下面几种功能：
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
因此有简单的实现方法。
package main
import "fmt"
type Trie struct {
//结束标志
isEnd bool
//子节点使用大小为26的数组存储
children [26]*Trie
}
func Constructor() Trie {
return Trie{}
}
//插入节点
func (this *Trie) Insert(word string) {
node := this
//遍历单词，确定依次向下的节点
for _, ch := range word {
//确定路径位置，即应该放到数组哪个位置
path := ch - 'a'
if node.children[path] == nil {
//若不存在这个位置，则创建
node.children[path] = &Trie{}
}
//向下移动
node = node.children[path]
}
//结尾标志置位true
node.isEnd = true
}
//搜索前缀
func (this *Trie) SearchPrefix(prefix string) *Trie {
node := this
for _, ch := range prefix {
path := ch - 'a'
if node.children[path] == nil {
return nil
}
node = node.children[path]
}
return node
}
//若能找到前缀并且isEnd为true，则找到这个单词
func (this *Trie) Search(word string) bool {
node := this.SearchPrefix(word)
return node != nil && node.isEnd
}
func (this *Trie) StartsWith(prefix string) bool {
return this.SearchPrefix(prefix) != nil
}
func main() {
T := Constructor()
T.Insert("hello")
T.Insert("how")
T.Insert("heihei")
if ok := T.Search("how"); ok {
fmt.Println("成功找到")
} else {
fmt.Println("meiyou找到")
}
}
通用实现：
type TrieNode struct {
pass int
end int
next [26]*TrieNode
}
type Trie struct {
root *TrieNode
}
// 初始化前缀树
func NewTrie() *Trie {
return &Trie{
root: &TrieNode{},
}
}
// 向前缀树中插入单词
func (t *Trie) Insert(word string) {
if len(word) == 0 {
return
}
node := t.root
node.pass++
for _, char := range word {
index := char - 'a'
if node.next[index] == nil {
node.next[index] = &TrieNode{}
}
node = node.next[index]
node.pass++
}
node.end++
}
// 查找单词是否在前缀树中存在
func (t *Trie) Search(word string) bool {
node := t.root
for _, char := range word {
index := char - 'a'
if node.next[index] == nil {
return false
}
node = node.next[index]
}
return node.end > 0
}
// 检查是否有以给定前缀开头的单词存在于前缀树中
func (t *Trie) StartsWith(prefix string) bool {
node := t.root
for _, char := range prefix {
index := char - 'a'
if node.next[index] == nil {
return false
}
node = node.next[index]
}
return node.pass > 0
}
// 获取以某个前缀开头的单词数量
func (t *Trie) CountWordsWithPrefix(prefix string) int {
node := t.root
for _, char := range prefix {
index := char - 'a'
if node.next[index] == nil {
return 0
}
node = node.next[index]
}
return node.pass
}
// 获取某个单词出现的次数
func (t *Trie) CountWordOccurrences(word string) int {
node := t.root
for _, char := range word {
index := char - 'a'
if node.next[index] == nil {
return 0
}
node = node.next[index]
}
return node.end
}
// 删除单词
func (t *Trie) Delete(word string) {
if!t.Search(word) {
return
}
node := t.root
node.pass--
for _, char := range word {
index := char - 'a'
child := node.next[index]
if child.pass == 1 {
// 如果经过这个子节点的次数为1，说明只有当前要删除的单词经过它，直接删除该子节点
node.next[index] = nil
return
}
child.pass--
if child.end > 0 && child.pass == 0 {
// 如果当前子节点是某个单词结尾且经过次数变为0了，说明要删除的单词是最后经过它的单词，将其end置0
child.end = 0
return
}
node = child
}
node.end--
}测试：
func main() {
trie := NewTrie()
trie.Insert("apple")
trie.Insert("app")
trie.Insert("banana")
println(trie.Search("apple"))
println(trie.Search("app"))
println(trie.Search("banana"))
trie.Delete("apple")
println("After deleting 'apple':")
println(trie.Search("apple"))
println(trie.CountWordsWithPrefix("app"))
println(trie.CountWordOccurrences("apple"))
trie.Delete("app")
println("After deleting 'app':")
println(trie.Search("app"))
println(trie.CountWordsWithPrefix("app"))
println(trie.CountWordOccurrences("app"))
}