Simple C++ implementation, utilizing 2 short common functions.


  • 0
    C
    class TrieNode {
    private:
    #define NUM_LETTERS (26)
        bool present;
        TrieNode* nodes[NUM_LETTERS];
        int charToInd(char ch) {return (ch - 'a');}
    public:
        TrieNode() : present(false), nodes() { for (int i=0; i<NUM_LETTERS; i++) nodes[i] = NULL; }
        ~TrieNode() { for (int i=0; i<NUM_LETTERS; i++) if (nodes[i]) delete nodes[i]; }
        bool Present() const {return present;}
        void Present(bool val) {present = val;}
        TrieNode*& operator[] (char ch) {return nodes[charToInd(ch)];}
    };
    
    class Trie {
        void put(TrieNode*& node, string& s, unsigned int lvl) {
            if (node == NULL) node = new TrieNode();
            if (lvl == s.length()) {
                node->Present(true);
            } else {
                put((*node)[s[lvl]], s, lvl+1);
            }
        }
        TrieNode* get(TrieNode *nd, string& s, unsigned int lvl) {
            if (nd == NULL) return NULL;
            if (lvl == s.length()) return nd;
            return (get((*nd)[s[lvl]], s, lvl+1));
        }
    public:
        Trie() {
            root = new TrieNode();
        }
        
        ~Trie() {
            delete root;
        }
    
        void insert(string s) {
            put(root, s, 0);
        }
    
        bool search(string key) {
            TrieNode *node = get(root, key, 0);
            return (node == NULL ? false : node->Present());
        }
    
        bool startsWith(string prefix) {
            return (get(root, prefix, 0) != NULL);
        }
    
    private:
        TrieNode* root;
    };

  • 0
    W

    how long is your run time? I'm trying to find better solution with less than 60ms. Thanks.


  • 0
    C

    72 ms when I tried just now.


Log in to reply
 

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