本文是前缀树模板
代码type Trie struct {
children [26]*Trie //当前字母的下一个字母是26个字母之一
isEnd bool //某个单词以当前字母结尾
}
func Constructor() Trie {
return Trie{}
}
func (t *Trie) Insert(word string) {
node := t //从根出发
for _, ch := range word {
ch -= 'a'
if node.children[ch] == nil { //如果这个字母不存在
node.children[ch] = &Trie{} //则新建这个字母
}
node = node.children[ch] //下一个字母从这个字母的位置开始找
}
node.isEnd = true //所有字母都插入完了，把最后一个字母的结束标志置为true
}
func (t *Trie) SearchPrefix(prefix string) *Trie {
node := t //从根出发
for _, ch := range prefix {
ch -= 'a'
if node.children[ch] == nil { //如果这个字母不存在
return nil //那就说明没有这个单词,直接返回
}
node = node.children[ch] //下一个字母从这个字母的位置开始找
}
return node //返回最后一个字母的地址
}
func (t *Trie) Search(word string) bool {
node := t.SearchPrefix(word) //最后一个字母的地址
return node != nil && node.isEnd == true //存在并且以这个字母结尾
}
func (t *Trie) StartsWith(prefix string) bool {
node := t.SearchPrefix(prefix) //最后一个字母的地址
return node != nil //存在
}