C++ solution, beats 79.41%


  • 1
    I
    class TrieNode {
    public:
        // Initialize your data structure here.
        TrieNode() : isSubstantial(false) {};
        TrieNode* kids[26] = { 0 };
        bool isSubstantial; 
    }; 
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string word) {
            TrieNode *cur = root;
            for (int i = 0; i < word.size(); i++) {
                if (cur->kids[word[i] - 'a'] == NULL) {
                    cur->kids[word[i] - 'a'] = new TrieNode();
                }
                cur = cur->kids[word[i] - 'a'];
            }
            cur->isSubstantial = true;
        }
    
        // Returns if the word is in the trie.
        bool search(string word) {
            TrieNode *cur = root;
            for (int i = 0; i < word.size() && cur; i++) {
                cur = cur->kids[word[i] - 'a'];
            }
            return cur && cur->isSubstantial;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            TrieNode *cur = root;
            for (int i = 0; i < prefix.size() && cur; i++) {
                cur = cur->kids[prefix[i] - 'a'];
            }
            return cur;
        }
    
    private:
        TrieNode* root;
    };

Log in to reply
 

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