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 mainimport "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]}//结尾标志置位truenode.isEnd = true
}//搜索前缀
func (this *Trie) SearchPrefix(prefix string) *Trie {node := thisfor _, 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  intnext [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.rootnode.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.rootfor _, 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.rootfor _, 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.rootfor _, 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.rootfor _, 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.rootnode.pass--for _, char := range word {index := char - 'a'child := node.next[index]if child.pass == 1 {// 如果经过这个子节点的次数为1，说明只有当前要删除的单词经过它，直接删除该子节点node.next[index] = nilreturn}child.pass--if child.end > 0 && child.pass == 0 {// 如果当前子节点是某个单词结尾且经过次数变为0了，说明要删除的单词是最后经过它的单词，将其end置0child.end = 0return}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"))
}