C++ solution, quite standard, no trick


  • 0
    D
    const int C_NUM = 26;
    class TrieNode {
    public:
        bool leaf;
        TrieNode* children[C_NUM];
        // Initialize your data structure here.
        TrieNode() {
            leaf = false;
            fill_n(children, C_NUM, nullptr);
        }
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
            root->leaf = true;
        }
    
        // Inserts a word into the trie.
        void insert(string s) {
            TrieNode* cur = root;
            int len = s.size(), i=0;
            if(len>0)
            {
                while(s[i] && cur->children[s[i] -'a']) 
                { 
                    cur = cur->children[s[i] -'a']; 
                    i++;
                }
                if(!s[i])
                {
                    cur->leaf = true; 
                }
                else
                {
                    while(s[i])
                    {
                        cur = cur->children[s[i] -'a'] = new TrieNode();
                        i++;    
                    }
                    cur->leaf = true;
                }
            }
        }
    
        // Returns if the word is in the trie.
        bool search(string key) {
            TrieNode* cur = root;
            int len = key.size(), i=0;
            if(len>0)
            {
                while(key[i] && cur->children[key[i] -'a']) 
                { 
                    cur = cur->children[key[i] -'a']; 
                    i++;
                }
                if(!key[i] && cur->leaf) return true;
            }
            return false;
            
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            TrieNode* cur = root;
            int len = prefix.size(), i=0;
            if(len>0)
            {
                while(prefix[i] && cur->children[prefix[i] -'a']) 
                { 
                    cur = cur->children[prefix[i] -'a']; 
                    i++;
                }
                if(prefix[i]) return false;
            }
            return true;
            
        }
    
    private:
        TrieNode* root;
    };
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie;
    // trie.insert("somestring");
    // trie.search("key");

Log in to reply
 

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