[Short Concise C++] Super easy to understand


  • 0
    H
    class TrieNode {
    private:
        // There are some words in this dictionary ends at this level.
        bool worde;
        // The next char in this word.
        vector<TrieNode*> nextc;
    
    public:
        TrieNode() {
            worde = false;
            nextc.resize(26);
            for (TrieNode* it : nextc) it = nullptr;
        }
        
        void insert (const string &s, int index) {
            if (index == s.size()) worde = true;
            else {
                int nextidx = s[index] - 'a';
                if (!nextc[nextidx]) nextc[nextidx] = new TrieNode();
                nextc[nextidx]->insert(s, index + 1);
            }
        }
        
        // If startwith is false, we need to find the specific word in this Trie tree (the *worde* is true after the last char).
        // Else, we only need to find is there a valid path along the prefix nodes.
        bool find (const string &s, int index, bool startwith) {
            if (index == s.size()) return startwith || worde;
            else {
                int nextidx = s[index] - 'a';
                if (nextc[nextidx]) return nextc[nextidx]->find(s, index + 1, startwith);
                return false;
            }
        }
    };
    
    class Trie {
    public:
        Trie() { root = new TrieNode(); }
        void insert(string word) { root->insert(word, 0); }
        bool search(string word) { return root->find(word, 0, false); }
        bool startsWith(string prefix) { return root->find(prefix, 0, true); }
    
    private:
        TrieNode* root;
    };
    

Log in to reply
 

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