-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path208.implement-trie-prefix-tree.cpp
More file actions
108 lines (99 loc) · 2.88 KB
/
208.implement-trie-prefix-tree.cpp
File metadata and controls
108 lines (99 loc) · 2.88 KB
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
// Tag: Hash Table, String, Design, Trie
// Time: O(N)
// Space: O(L)
// Ref: -
// Note: -
// A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
// Implement the Trie class:
//
// Trie() Initializes the trie object.
// void insert(String word) Inserts the string word into the trie.
// boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
// boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
//
//
// Example 1:
//
// Input
// ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
// [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
// Output
// [null, null, true, false, true, null, true]
//
// Explanation
// Trie trie = new Trie();
// trie.insert("apple");
// trie.search("apple"); // return True
// trie.search("app"); // return False
// trie.startsWith("app"); // return True
// trie.insert("app");
// trie.search("app"); // return True
//
//
// Constraints:
//
// 1 <= word.length, prefix.length <= 2000
// word and prefix consist only of lowercase English letters.
// At most 3 * 104 calls in total will be made to insert, search, and startsWith.
//
//
class TrieNode {
public:
vector<TrieNode *> children;
bool is_word;
TrieNode(): is_word(false) {
children = vector<TrieNode *>(26, nullptr);
}
~TrieNode() {
for (TrieNode* child : children) {
delete child;
}
}
};
class Trie {
public:
TrieNode *root;
Trie() {
root = new TrieNode();
}
~Trie() {
delete root;
}
void insert(string word) {
TrieNode *cur = root;
for (auto x: word) {
if (!cur->children[x - 'a']) {
cur->children[x - 'a'] = new TrieNode();
}
cur = cur->children[x - 'a'];
}
cur->is_word = true;
}
bool search(string word) {
TrieNode* cur = root;
for (auto x: word) {
if (!cur->children[x - 'a']) {
return false;
}
cur = cur->children[x - 'a'];
}
return cur->is_word;
}
bool startsWith(string prefix) {
TrieNode *cur = root;
for (auto x: prefix) {
if (!cur->children[x - 'a']) {
return false;
}
cur = cur->children[x - 'a'];
}
return true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/