65ms cc code


  • 0
    M

    I remove the char in struct TrieNode, as we don't really use it here.
    When I move search(const string&, const int&, TrieNode*) from public to private,
    the speed improves a lot, why?

    struct TrieNode {
        TrieNode* children_[26];
        bool is_word_;
        TrieNode() : is_word_(false) {
            memset(children_, 0, sizeof(TrieNode*) * 26);
        }
    };
    
    class WordDictionary {
    public:
        WordDictionary() {
            root_ = new TrieNode();
        }
        // Adds a word into the data structure.
        void addWord(string word) {
            if (word.empty()) return;
            TrieNode* tmp = root_;
            for (const char& c : word) {
                if (tmp->children_[c-'a'] == nullptr) {
                    tmp->children_[c-'a'] = new TrieNode();
                }
                tmp = tmp->children_[c-'a'];
            }
            tmp->is_word_ = true;
        }
    
        // 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, 0, root_);
        }
        
    private:
        TrieNode* root_;
        bool search(const string& word, const int& start_idx, TrieNode* now_node) {
            for (int idx = start_idx; idx < word.size(); ++idx) {
                const char& c = word[idx];
                if (c == '.') {
                    for (int i = 0; i < 26; ++i) {
                        if (now_node->children_[i] != nullptr)
                            if (search(word, idx+1, now_node->children_[i])) return true;
                    }
                    return false;
                } else {
                    if (now_node->children_[c-'a'] == nullptr) return false;
                    now_node = now_node->children_[c-'a'];
                }
            }
            return now_node->is_word_;
        }
    };
    
    

Log in to reply
 

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