Trie Implementation

Leetcode use.

class Trie {
public:
    void insert(string word) {
        auto p = _root;
        for(char c : word) {
            if(p->child[c-'a'] == nullptr) 
                p->child[c-'a'] = new Node();
            p = p->child[c-'a'];
        }
        p->has = true;
    }
    bool search(string word) {
        auto p = searchNode(word);
        return p == nullptr ? false : p->has;
    }
    bool startsWith(string prefix) {
        return searchNode(prefix) != nullptr;
    }
    Trie() : _root(new Node()) {}
private:
    struct Node {
        bool has = false;
        Node *child[26] = {0};
    };
    Node *searchNode(const string &word) const {
        auto p = _root;
        for(char c : word) {
            if(p->child[c-'a'] == nullptr) return nullptr;
            p = p->child[c-'a'];
        }
        return p;
    }
    Node *_root;
};

Leave a Reply

Your email address will not be published. Required fields are marked *

8 + eighteen =

Note: Commenter is allowed to use '@+User+:' to automatically notify your reply to other commenter.