-
Notifications
You must be signed in to change notification settings - Fork 2.3k
/
0208-implement-trie-prefix-tree.swift
58 lines (50 loc) · 1.35 KB
/
0208-implement-trie-prefix-tree.swift
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
class TrieNode {
var children: [Character: TrieNode]
var isWord: Bool
init() {
children = [:]
isWord = false
}
}
class Trie {
var head: TrieNode
init() {
head = TrieNode()
}
func insert(_ word: String) {
var itr = head
for char in word {
guard let child = itr.children[char]
else {
let newNode = TrieNode()
itr.children[char] = newNode
itr = newNode
continue
}
itr = child
}
itr.isWord = true
}
// Helper function to combine word and prefix searching
private func search(word: String, isPrefixCheck: Bool) -> Bool {
var itr = head
for char in word {
guard let child = itr.children[char] else { return false }
itr = child
}
return isPrefixCheck ? true : itr.isWord
}
func search(_ word: String) -> Bool {
search(word: word, isPrefixCheck: false)
}
func startsWith(_ prefix: String) -> Bool {
search(word: prefix, isPrefixCheck: true)
}
}
/**
* Your Trie object will be instantiated and called as such:
* let obj = Trie()
* obj.insert(word)
* let ret_2: Bool = obj.search(word)
* let ret_3: Bool = obj.startsWith(prefix)
*/