Trie树（前缀树）
一句话说明
Trie 的本质是共享前缀，所以字符串查找、前缀匹配都能被压到很短的路径上。
Go 代码
type TrieNode struct {
children map[rune]*TrieNode
isEnd bool
}
type Trie struct {
root *TrieNode
}
func Constructor() Trie {
return Trie{root: &TrieNode{children: map[rune]*TrieNode{}}}
}
func (t *Trie) Insert(word string) {
node := t.root
for _, ch := range word {
if node.children[ch] == nil {
node.children[ch] = &TrieNode{children: map[rune]*TrieNode{}}
}
node = node.children[ch]
}
node.isEnd = true
}
func (t *Trie) Search(word string) bool {
node := t.root
for _, ch := range word {
next := node.children[ch]
if next == nil {
return false
}
node = next
}
return node.isEnd
}
func (t *Trie) StartsWith(prefix string) bool {
node := t.root
for _, ch := range prefix {
next := node.children[ch]
if next == nil {
return false
}
node = next
}
return true
}