快速找前缀
package main
const MAXN = 150000
var tree [MAXN][26]int
var end [MAXN]int
var pass [MAXN]int
var cnt int
type Trie struct{}
func Constructor() Trie {
for i := 0; i < MAXN; i++ {
for j := range 26{
tree[i][j] = 0
}
end[i] = 0
pass[i] = 0
}
cnt = 1
return Trie{}
}
func (this *Trie) Insert(word string) {
next := 1
pass[next]++
for _, ch := range word {
p := ch - 'a'
if tree[next][p] == 0 {
cnt++
tree[next][p] = cnt
}
next = tree[next][p]
pass[next]++
}
end[next]++
}
func (this *Trie) Search(word string) bool {
next := 1
for _, ch := range word {
p := ch - 'a'
if tree[next][p] == 0 {
return false
}
next = tree[next][p]
}
return end[next] > 0
}
func (this *Trie) StartsWith(prefix string) bool {
next := 1
for _, ch := range prefix {
p := ch - 'a'
if tree[next][p] == 0 {
return false
}
next = tree[next][p]
}
return pass[next] > 0
}