APP
1.什么是Trie
2.Trie的新增/查询/prefix
package main
type Node struct {
isWord bool
next map[string]*Node
}
type trie struct {
root *Node
}
func generateNode() *Node {
return &Node{next: make(map[string]*Node)}
}
func NewTrie() *trie {
return &trie{
root: generateNode(),
}
}
func (t *trie) Insert(word string) {
cur := t.root
for _, w := range []rune(word) {
wStr := string(w)
if cur.next[wStr] == nil {
cur.next[wStr] = generateNode()
}
cur = cur.next[wStr]
}
cur.isWord = true
}
func (t *trie) Search(word string) bool{
cur := t.root
for _,w := range []rune(word){
wStr := string(w)
if cur.next[wStr]==nil{
return false
}
cur=cur.next[wStr]
}
return cur.isWord
}
func (t *trie) Prefix(prefix string) bool{
cur := t.root
for _,w := range []rune(prefix){
wStr := string(w)
if cur.next[wStr]==nil{
return false
}
cur=cur.next[wStr]
}
return true
}
3.Trie例题
3.1实现trie树
https://leetcode.cn/problems/implement-trie-prefix-tree/
package main
type Node struct {
isWord bool
next map[string]*Node
}
type Trie struct {
root *Node
}
func Constructor() Trie {
return Trie{root: generateNode()}
}
func generateNode() *Node {
return &Node{next: make(map[string]*Node)}
}
func (this *Trie) Insert(word string) {
cur := this.root
for _,w :=range word{
wStr := string(w)
if cur.next[wStr] ==nil{
cur.next[wStr] = generateNode()
}
cur = cur.next[wStr]
}
cur.isWord = true
}
func (this *Trie) Search(word string) bool {
cur := this.root
for _,w :=range word{
wStr := string(w)
if cur.next[wStr] ==nil{
return false
}
cur = cur.next[wStr]
}
return cur.isWord
}
func (this *Trie) StartsWith(prefix string) bool {
cur := this.root
for _,w :=range prefix{
wStr := string(w)
if cur.next[wStr] ==nil{
return false
}
cur = cur.next[wStr]
}
return true
}
/**
* Your Trie object will be instantiated and called as such:
* obj := Constructor();
* obj.Insert(word);
* param_2 := obj.Search(word);
* param_3 := obj.StartsWith(prefix);
*/
3.2添加与搜索单词
package main
import "fmt"
type Node struct {
next map[string]*Node
isWord bool
}
type WordDictionary struct {
root *Node
}
func Constructor() WordDictionary {
return WordDictionary{root: generateNode()}
}
func generateNode() *Node {
return &Node{next: make(map[string]*Node)}
}
func (this *WordDictionary) AddWord(word string) {
cur := this.root
for _, w := range []rune(word) {
wStr := string(w)
if cur.next[wStr] == nil {
cur.next[wStr] = generateNode()
}
cur = cur.next[wStr]
}
cur.isWord = true
}
func (this *WordDictionary) Search(word string) bool {
return this.searchR(word, this.root, 0)
}
func (this *WordDictionary) searchR(word string, node *Node, index int) bool {
if index == len(word) {
return node.isWord
}
c := string([]rune(word)[index])
if c != "." {
if node.next[c] == nil {
return false
} else {
return this.searchR(word, node.next[c], index+1)
}
}else{
for w,_ :=range node.next{
if this.searchR(word, node.next[w], index+1){
return true
}
}
return false
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* obj := Constructor();
* obj.AddWord(word);
* param_2 := obj.Search(word);
*/
func main() {
obj := Constructor()
obj.AddWord("bad")
obj.AddWord("dad")
obj.AddWord("mad")
fmt.Println(obj.Search("pad"))
fmt.Println(obj.Search("bad"))
fmt.Println(obj.Search(".ad"))
fmt.Println(obj.Search("b.."))
}
3.3Map Sum
type Node struct {
next map[string]*Node
val int
}
type MapSum struct {
root *Node
}
func generateNode() *Node {
return &Node{next: make(map[string]*Node)}
}
func Constructor() MapSum {
return MapSum{root: generateNode()}
}
func (this *MapSum) Insert(key string, val int) {
cur := this.root
for _,w :=range []rune(key){
wStr :=string(w)
if cur.next[wStr]==nil{
cur.next[wStr] = generateNode()
}
cur = cur.next[wStr]
}
cur.val = val
}
func (this *MapSum) Sum(prefix string) int {
cur := this.root
for _,w :=range []rune(prefix){
wStr := string(w)
if cur.next[wStr]==nil{
return 0
}
cur = cur.next[wStr]
}
return this.sumR(cur)
}
func (this *MapSum)sumR(node *Node)int{
if len(node.next)==0{
return node.val
}
res := node.val
for _,n :=range node.next{
res += this.sumR(n)
}
return res
}
/**
* Your MapSum object will be instantiated and called as such:
* obj := Constructor();
* obj.Insert(key,val);
* param_2 := obj.Sum(prefix);
*/
本文摘自 ：https://blog.51cto.com/u
