C++ solution, :)


  • 0
    E
    class TrieNode {
    public:
        // Initialize your data structure here.
        TrieNode() : count(0), exist(false) {
            memset(this->next, 0, sizeof(this->next));
        }
        
        int count; // Number of words that start with this prefix;
        bool exist; // if a word exist here;
        TrieNode *next[26];
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string s) {
            if (s.empty()) return;
            TrieNode *n = root;
            for (int i = 0; i < s.length(); ++i) {
                if (!n->next[s[i] - 'a']) n->next[s[i] - 'a'] = new TrieNode();
                n = n->next[s[i] - 'a'];
                ++n->count;
            }
            n->exist = true;
        }
    
        // Returns if the word is in the trie.
        bool search(string key) {
            TrieNode *n = root;
            for (int i = 0; i < key.length(); ++i) {
                if (!n->next[key[i] - 'a']) return false;
                n = n->next[key[i] - 'a'];
            }
            return n->exist;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            TrieNode *n = root;
            for (int i = 0; i < prefix.length(); ++i) {
                if (!n->next[prefix[i] - 'a']) return false;
                n = n->next[prefix[i] - 'a'];
            }
            return n->count > 0;
        }
    
    private:
        TrieNode* root;
    };

  • 0
    W

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


Log in to reply
 

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