Why is my solution so slow?


  • 0
    L

    Are the smart pointers the reason why my code is running much slower than the others? It's below 1%.... :(

    class Trie {
    public:
        /** Initialize your data structure here. */
        struct TrieNode {
            bool isWord = false;
            vector<shared_ptr<TrieNode>> arr; // a~z
            TrieNode() {
                for (int i = 0; i < 26; i++) {
                    arr.push_back(shared_ptr<TrieNode>(nullptr));
                }
    	    }      
        };
        
        Trie() {
            root = shared_ptr<TrieNode>(new TrieNode);
        }
        
        /** Inserts a word into the trie. */
        void insert(string word) {
            if (word.empty() == true) return;
            shared_ptr<TrieNode>  cur = root;
            for (int i = 0; i<word.size(); i++) {
                if (i != word.size() - 1) {
                    if (cur->arr[word[i] - 'a'] != nullptr) {
                        cur = cur->arr[word[i] - 'a'];
                    }
                    else {
                        cur->arr[word[i] - 'a'] = shared_ptr<TrieNode>(new TrieNode);
                        cur = cur->arr[word[i] - 'a'];
                    }
                }
                else {
                    if (cur->arr[word[i] - 'a'] != nullptr) {
                        cur = cur->arr[word[i] - 'a'];
                        cur->isWord = true;
                    }
                    else {
                        cur->arr[word[i] - 'a'] = shared_ptr<TrieNode>(new TrieNode);
                        cur = cur->arr[word[i] - 'a'];
                        cur->isWord = true;
                    }
                }
            }
        }
        
        /** Returns if the word is in the trie. */
        bool search(string word) {
            if (word.empty() == true) return true;
    	    shared_ptr<TrieNode> cur = root;
    	    for (int i = 0; i < word.size(); i++) {
    	    	if (cur->arr[word[i] - 'a'] == nullptr) return false;
    	    	else {
    	    		cur = cur->arr[word[i] - 'a'];
    		    }
    	    }
    	    return cur->isWord;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        bool startsWith(string prefix) {
            if (prefix.empty() == true) return true;
    	    shared_ptr<TrieNode> cur = root;
    	    for (int i = 0; i < prefix.size(); i++) {
    	    	if (cur->arr[prefix[i] - 'a'] == nullptr) return false;
    	    	else {
    	    		cur = cur->arr[prefix[i] - 'a'];
    		    }
    	    }
    	    return true;
        }
    private:
        shared_ptr<TrieNode> root;
    };
    
    

Log in to reply
 

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