Skip to content

Instantly share code, notes, and snippets.

@dennisbot
Created June 23, 2017 17:03
Show Gist options
  • Save dennisbot/b37b2d4edcb5be35b7c540bb4dfea90e to your computer and use it in GitHub Desktop.
Save dennisbot/b37b2d4edcb5be35b7c540bb4dfea90e to your computer and use it in GitHub Desktop.
Trie.cpp
template <typename T>
class Trie {
private:
T count;
Trie<T> *next[26];
public:
Trie() {
count = T();
for (int i = 0; i < 26; i++) next[i] = NULL;
}
~Trie() {
for (int i = 0; i < 26; i++) delete next[i];
}
void add(string w) {
if (w.size() == 0) return;
int pos = w[0] - 'a';
if (next[pos] == NULL)
next[pos] = new Trie<int>();
next[pos]->count++;
next[pos]->add(w.substr(1));
}
int find(string w) {
int res = 0, pos;
if (w.size() && next[w[0] - 'a'] != NULL)
return next[w[0] - 'a']->find(w.substr(1));
if (w.size()) return 0;
return this->count;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment