forked from Nistha-tech/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
s1.cpp
39 lines (39 loc) · 993 Bytes
/
s1.cpp
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
// OJ: https://leetcode.com/problems/implement-trie-prefix-tree/
// Author: github.com/lzl124631x
// Time: O(W) for insert/search/startsWith
// Space:
// insert: O(W)
// search/startsWith: O(1)
class TrieNode {
public:
TrieNode *next[26] = {};
int count = 0;
};
class Trie {
private:
TrieNode root;
TrieNode* searchToNode(string &prefix) {
auto node = &root;
for (char c : prefix) {
if (!node->next[c - 'a']) return NULL;
node = node->next[c - 'a'];
}
return node;
}
public:
void insert(string word) {
auto node = &root;
for (char c : word) {
if (!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
node = node->next[c - 'a'];
}
node->count++;
}
bool search(string word) {
auto node = searchToNode(word);
return node && node->count;
}
bool startsWith(string prefix) {
return searchToNode(prefix);
}
};