-
Notifications
You must be signed in to change notification settings - Fork 0
/
trie.go
68 lines (61 loc) · 1.4 KB
/
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
package main
import "fmt"
type Node struct {
children [26]*Node
wordEnd bool
}
type Trie struct {
root *Node
}
func (trie *Trie) insert(word string) {
currentNode := trie.root
for _, letter := range word {
charIndex := letter - 'a' //Find the index to which the letter should be inserted. "letter" gives ascii value of the alphabet
if currentNode.children[charIndex] == nil {
currentNode.children[charIndex] = &Node{}
}
currentNode = currentNode.children[charIndex]
}
currentNode.wordEnd = true
}
func (trie *Trie) search(word string) {
currentNode := trie.root
for _, letter := range word {
charIndex := letter - 'a'
if currentNode.children[charIndex] == nil {
fmt.Println(word, "is not in trie")
return
}
currentNode = currentNode.children[charIndex]
}
if currentNode.wordEnd {
fmt.Println(word, "found in trie")
} else {
fmt.Println(word, "is not in trie")
}
}
func (trie *Trie) remove(word string) {
currentNode := trie.root
for _, letter := range word {
charIndex := letter - 'a'
if currentNode.children[charIndex] == nil {
fmt.Println(word, "is not in trie")
return
}
currentNode = currentNode.children[charIndex]
}
if len(currentNode.children) == 0 {
currentNode = nil
return
}
currentNode.wordEnd = false
}
func main() {
t := &Trie{root: &Node{}}
t.insert("hello")
t.insert("hi")
t.search("hello")
t.remove("hello")
t.search("hi")
t.remove("hi")
}