My 56ms C++ solution explained


  • 2
    C

    A canonical solution employs vector or C-array for alphabet lookup, these implementations usually give a runtime of 64ms ~ 76ms if correctly implemented.

    Remember that contiguous memory structure like vector/array always has a better memory/cache locality than list-based structure, which gets a better performance as a result. Consider that our previous implementations are exactly all based on list, therefore we can improve the runtime even further.

    Instead of allocating TrieNode on ad-hoc, a preserved vector of TrieNode is used. The elements of next array in TrieNode just point to nodes in that vector. Next time a new TrieNode shall be created, we emplace back into the vector. This trick gives me 56ms in runtime, very nice. Another benefit is that we don't need to worry about reclaiming the memory. One caveat though is that the size of vector must be large enough in pre-allocation, otherwise all pointers in TrieNode become invalidated once some emplace back triggers the vector to resize.

    The code can be found here

    How did you achieved <= 56ms in C++ for this problem? Your comments are highly welcomed.


  • 0
    P
    class TrieNode {
    private:
        TrieNode* data[27]; // extra for ""
    public:
        // Initialize your data structure here.
        TrieNode() {
            memset((void*)data, 0, sizeof(data));
        }
        
        void append(int start, const char* word, int N) {
            TrieNode* root = this;
            while (start < N) {
                int c = word[start++]-'a';
                if (!root->data[c]) {
                    root->data[c] = new TrieNode();
                }
                root = root->data[c];
            }
            if (!root->data[26]) {
                root->data[26] = new TrieNode();
            }
        }
        
        bool search(int start, const char* word, int N, bool full) const {
            const TrieNode* root = this;
            while (start < N) {
                int c = word[start++]-'a';
                if (!root->data[c])
                    return false;
                root = root->data[c];
            }
            return !full || root->data[26];
        }
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(const string& word) {
            root->append(0, word.c_str(), word.size());
        }
    
        // Returns if the word is in the trie.
        bool search(const string& word) {
            return root->search(0, word.c_str(), word.size(), true);
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(const string& prefix) {
            return root->search(0, prefix.c_str(), prefix.size(), false);
        }
    
    private:
        TrieNode* root;
    };
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie;
    // trie.insert("somestring");
    // trie.search("key");

  • 0
    P

    The running time for the above code is 52ms~56ms.


Log in to reply
 

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