76 ms modern C++ solution (plus a non-leaking version)


  • 0
    R

    Here's a trie-based solution, which doesn't leak due to using unique_ptr. Note that the runtime seemingly includes the destruction time. Thus the run time is 156ms.

    class WordDictionary {
    public:
        struct PrefixNode {
            bool isTerminal = false;
            std::array<unique_ptr<PrefixNode>, 'z' - 'a' + 1> children;
        };
    
        unique_ptr<PrefixNode> head;
    
        WordDictionary()
            : head(new PrefixNode())
        {}
    
    
        // Adds a word into the data structure.
        void addWord(string word) {
            PrefixNode* cur = head.get();
            for (int i = 0; i < word.size(); ++i) {
                auto& child = cur->children[word[i] - 'a'];
                if (!child) {
                    child.reset(new PrefixNode());
                }
    
                cur = child.get();
            }
            cur->isTerminal = true;
        }
    
        bool search(const string& word, PrefixNode* cur, int curIndex)
        {
            while (true) {
                if (curIndex == word.size()) {
                    return cur->isTerminal;
                }
        
                if (word[curIndex] == '.') {
                    for (auto& childPtr : cur->children) {
                        if (!childPtr) {
                            continue;
                        }
                        if (search(word, childPtr.get(), curIndex + 1)) {
                            return true;
                        }
                    }
                    return false;
                } else {
                    const auto& child = cur->children[word[curIndex] - 'a'];
                    if (!child) {
                        return false;
                    }
                    cur = child.get();
                    curIndex++;
                }
            }
        }
    
        // Returns if the word is in the data structure. A word could
        // contain the dot character '.' to represent any one letter.
        bool search(string word) {
            return search(word, head.get(), 0);
        }
    };
    

    Using raw pointers, runtime drops down to 76ms:

    class WordDictionary {
    public:
        struct PrefixNode {
            bool isTerminal = false;
            std::array<PrefixNode*, 'z' - 'a' + 1> children;
        };
    
        PrefixNode* head;
    
        WordDictionary()
            : head(new PrefixNode())
        {}
    
    
        // Adds a word into the data structure.
        void addWord(string word) {
            PrefixNode* cur = head;
            for (int i = 0; i < word.size(); ++i) {
                auto& child = cur->children[word[i] - 'a'];
                if (!child) {
                    child = new PrefixNode();
                }
    
                cur = child;
            }
            cur->isTerminal = true;
        }
    
        bool search(const string& word, PrefixNode* cur, int curIndex)
        {
            while (true) {
                if (curIndex == word.size()) {
                    return cur->isTerminal;
                }
        
                if (word[curIndex] == '.') {
                    for (auto& childPtr : cur->children) {
                        if (!childPtr) {
                            continue;
                        }
                        if (search(word, childPtr, curIndex + 1)) {
                            return true;
                        }
                    }
                    return false;
                } else {
                    const auto& child = cur->children[word[curIndex] - 'a'];
                    if (!child) {
                        return false;
                    }
                    cur = child;
                    curIndex++;
                }
            }
        }
    
        // Returns if the word is in the data structure. A word could
        // contain the dot character '.' to represent any one letter.
        bool search(string word) {
            return search(word, head, 0);
        }
    };

Log in to reply
 

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