C++ 42ms clean solution


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

Log in to reply
 

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