My Super Short C++ (50ms)


  • 0
    K
    class Node {
        public:
        bool isLeaf = false;
        vector<Node*> children;
        Node() {
            children.assign(26, nullptr);
        }
        Node* getChild(char val_) {
            return children[val_-'a']; 
        }
        Node* makeChild(char val_) {
            int pos = val_-'a';
            if (children[pos] == nullptr)   children[pos] = new Node();
            return children[pos];
        }
    };
    
    class Trie {
    public:
        /** Initialize your data structure here. */
        Trie() {
            root = new Node();
        }
        
        /** Inserts a word into the trie. */
        void insert(string word) {
            Node* curr = root;
            for (auto c : word) curr = curr->makeChild(c);
            curr->isLeaf = true;
        }
        
        /** Returns if the word is in the trie. */
        bool search(string word) {
            Node* ret = findHelper(word);
            return ret != nullptr && ret->isLeaf;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        bool startsWith(string prefix) {
            return findHelper(prefix) != nullptr;  
        }
        
        Node* findHelper(string s) {
            Node* curr = root;
            for (auto c : s) {
                if ((curr = curr->getChild(c)) == nullptr) return nullptr;
            }
            return curr;
        }
        Node* root;
    };
    

Log in to reply
 

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