This repository has been archived by the owner on Dec 17, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Trie.go
113 lines (82 loc) · 2.29 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
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/*
Trie Tree implementation
Project: httsp://github.com/eng-gabrielscardoso/trie-tree
Under MIT Licence
Maintainer: Gabriel Santos Cardoso
*/
/*
Package core provides essential abstractions for building a trie tree
*/
package core
/*
Package strings implements simple functions to manipulate UTF-8 encoded strings.
*/
import s "strings"
/*
This struct provides a Trie tree structure
*/
type Trie struct {
root *Node
}
/*
This method provides a new Trie tree struture
# For each new Trie tree created the root is initialised with the value "\000" that represents the nil value in UNICODE table
@return &Trie: *Trie
*/
func NewTrie() *Trie {
root := NewNode("\000")
return &Trie{root: root}
}
/*
This method is reponsible for insert a new element into the Trie
@param word: string - word to be inserted into the Trie
@return _, error: nil, _ - if something went wrong nothing happens, otherwise thats OK
*/
func (t *Trie) Insert(word string) error {
current := t.root
strippedWord := s.ToLower(s.ReplaceAll(word, " ", ""))
for i := 0; i < len(strippedWord); i++ {
index := strippedWord[i] - 'a'
if current.children[index] == nil {
current.children[index] = NewNode(string(strippedWord[i]))
}
current = current.children[index]
}
return nil
}
/*
This methods is responsible for search a word into the Trie
@param word: string - word to be searched into the Trie
@return bool - if found, return true, otherwise return false
*/
func (t *Trie) SearchWord(word string) bool {
current := t.root
strippedWord := s.ToLower(s.ReplaceAll(word, " ", ""))
for i := 0; i < len(strippedWord); i++ {
index := strippedWord[i] - 'a'
if current == nil || current.children[index] == nil {
return false
}
}
return true
}
/*
This methods is responsible for delete a word from the Trie
@param word: string - word to be deleted from the Trie
@return bool - if deleted, return true, otherwise return false
*/
func (t *Trie) RemoveWord(word string) bool {
current := t.root
strippedWord := s.ToLower(s.ReplaceAll(word, " ", ""))
for i := 0; i < len(strippedWord); i++ {
index := strippedWord[i] - 'a'
if current.children[index] != nil {
if current.children[index].char == strippedWord {
current.children[index] = nil
return true
}
}
current = current.children[index]
}
return false
}