Trie.cpp

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;
    }
};