class TrieNode {
public:
bool exist;
TrieNode* children[
26];
TrieNode() {
exist =
false;
memset(children, 0,
sizeof(children));
}
};
class Trie {
public:
Trie() {
root =
new TrieNode();
}
void insert(
string word) {
TrieNode* cur =
root;
for(
char c: word){
if(cur->children[c-
'a']==NULL) cur->children[c-
'a'] =
new TrieNode();
cur = cur->children[c-
'a'];
}
cur->exist =
true;
}
// Returns if the word is in the trie.
bool search(
string word) {
TrieNode* cur =
root;
for(
char c: word){
if(cur->children[c-
'a']==NULL)
return false;
cur = cur->children[c-
'a'];
}
return (cur->
exist);
}
bool startsWith(
string prefix) {
TrieNode* cur =
root;
for(
char c: prefix){
if(cur->children[c-
'a']==NULL)
return false;
cur = cur->children[c-
'a'];
}
return true;
}
private:
TrieNode*
root;
};
如果没有用memset,在有些编译器上不会给children赋初值。然后这个代码就run time error 了额....
转载于:https://www.cnblogs.com/XingyingLiu/p/5224556.html