-
Notifications
You must be signed in to change notification settings - Fork 1
/
day_56_trie.go
94 lines (77 loc) · 1.53 KB
/
day_56_trie.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package main
import "fmt"
type trie_node struct {
children map[rune]*trie_node
value interface{}
}
func new() *trie_node {
return &trie_node{
children: make(map[rune]*trie_node),
}
}
func (trie *trie_node) contains(key string) bool {
node := trie
for _, ch := range key {
node = node.children[ch]
if node == nil {
return false
}
}
return node.value != nil
}
func (trie *trie_node) insert(key string, value int) bool {
node := trie
for _, ch := range key {
child, _ := node.children[ch]
if child == nil {
child = new()
node.children[ch] = child
}
node = child
}
is_new := node.value == nil
node.value = value
return is_new
}
type node_str struct {
node *trie_node
part rune
}
func (trie *trie_node) del(key string) bool {
var path []node_str
node := trie
for _, ch := range key {
path = append(path, node_str{part: ch, node: node})
node = node.children[ch]
if node == nil {
return false
}
}
node.value = nil
if len(node.children) == 0 {
for i := len(path) - 1; i >= 0; i-- {
parent := path[i].node
part := path[i].part
delete(parent.children, part)
if parent.value != nil || !(len(parent.children) == 0) {
break
}
}
}
return true
}
func main() {
arr := []string{"k", "kr", "kri", "kris", "krish", "krishn", "krishna"}
tree := new()
for i, key := range arr {
tree.insert(key, i)
}
tree.del("krish")
var contains string
if tree.contains("kris") {
contains = "contains"
} else {
contains = "does not contain"
}
fmt.Printf(" %v %v\n", contains, "kris")
}