-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtrie.go
124 lines (109 loc) · 2.44 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
114
115
116
117
118
119
120
121
122
123
124
package trie
// Trie represents trie tree data structure
//
// Use NewTrie to create new tree
type Trie struct {
root *trieNode
}
type trieNode struct {
isWord bool
children map[rune]*trieNode
}
// NewTrie creates new tree along with its root node
func NewTrie() *Trie {
return &Trie{root: &trieNode{children: map[rune]*trieNode{}}}
}
// Insert inserts word to the tree. Each letter becomes tree node (if not exists)
func (t *Trie) Insert(word ...string) {
for _, w := range word {
t.insertWord(w)
}
}
func (t *Trie) insertWord(word string) {
current := t.root
for _, letter := range word {
node, ok := current.children[letter]
if !ok {
node = &trieNode{children: map[rune]*trieNode{}}
current.children[letter] = node
}
current = node
}
current.isWord = true
}
func (t *trieNode) nodeByPrefix(word string) *trieNode {
var ok bool
current := t
for _, letter := range word {
current, ok = current.children[letter]
if !ok {
return nil
}
}
return current
}
// HasWord checks if the tree has word. It needs the complete match. For prefix check use HasPrefix
func (t *Trie) HasWord(word string) bool {
node := t.root.nodeByPrefix(word)
if node == nil {
return false
}
return node.isWord
}
// HasPrefix check if the tree has words with this prefix
func (t *Trie) HasPrefix(word string) bool {
node := t.root.nodeByPrefix(word)
if node == nil {
return false
}
return true
}
// WordsByPrefix returns all words from the tree with this prefix
func (t *Trie) WordsByPrefix(prefix string) []string {
return t.root.wordsByPrefix(prefix)
}
func (t *trieNode) wordsByPrefix(prefix string) []string {
node := t.nodeByPrefix(prefix)
if node == nil {
return nil
}
return node.travers(prefix)
}
type traversHelper struct {
node *trieNode
prefix string
}
type stack []*traversHelper
func (s *stack) push(th *traversHelper) {
*s = append(*s, th)
}
func (s *stack) pop() *traversHelper {
if len(*s) > 0 {
n := len(*s) - 1
elem := (*s)[n]
*s = (*s)[:n]
return elem
}
return nil
}
func (t *trieNode) travers(prefix string) []string {
var words []string
if t.isWord {
words = []string{prefix}
}
stack := stack{{t, prefix}}
for {
th := stack.pop()
if th == nil {
return words
}
for letter, child := range th.node.children {
if child.isWord {
words = append(words, th.prefix+string(letter))
}
if len(child.children) > 0 {
stack.push(&traversHelper{child, th.prefix + string(letter)})
}
}
}
}