Neat C++ Solution. DRY


  • 0
    W

    Don't Repeat Yourself.

    class TrieNode {
    public:
        // Initialize your data structure here.
        TrieNode() {}
        TrieNode *next[26]{};
        bool is_leaf = false;
        TrieNode *get(char c) { return next[c - 'a']; }
        void add(char c) { next[c - 'a'] = new TrieNode; }
    };
    
    class Trie {
    public:
        Trie() : root(new TrieNode) { }
    
        // Inserts a word into the trie.
        void insert(const string &word) {
            auto p = root;
            for (auto c : word) {
                if (!p->get(c)) p->add(c);
                p = p->get(c);
            }
            p->is_leaf = true;
        }
    
        // Returns if the word is in the trie.
        bool search(const string &word) {
            auto node = find(word);
            return node && node->is_leaf;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(const string &prefix) {
            return find(prefix);
        }
    
    private:
        TrieNode* find(const string &prefix) {
            auto p = root;
            for (auto c : prefix) {
                p = p->get(c);
                if (!p) break;
            }
            return p;
        }
        TrieNode* root;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.