C++ Trie: Optimization?


  • 0
    A
    class TrieNode {
        bool isTerminal;
        vector<TrieNode*> children;
        
        public:
        TrieNode(){
            isTerminal = false;
            children.resize(26, NULL);
        }
        friend class WordDictionary;
    };
    
    
    
    class WordDictionary {
        TrieNode * root;
        public:
        WordDictionary(){
            root = new TrieNode();
        }
        void addWord(string word) {
            TrieNode* it = root;
            for(int i = 0; i < word.size(); i++){
                int index = word[i] - 'a';
                if(it->children[index] == NULL){
                    it->children[index] = new TrieNode();
                }
                
                it = it->children[index];
            }
            it->isTerminal = true;
        }
        
        
        bool search(string word) {
            TrieNode* it = root;
            for(int i = 0; i < word.size(); i++){
                if(word[i] == '.'){
                    for(int j = 0; j < 26; j++){
                        if(it->children[j]){
                            word[i] = 'a' + j;
                            if(search(word))
                                return true;
                        }
                    }
                    return false;
                }
                
                int index = word[i] - 'a';
                if(it->children[index] == NULL)
                    return false;
                it = it->children[index];
            }
            
            if(it->isTerminal)
                return true;
            return false;
        }
    };
    

    Hi, how can I improve this code? Mainly pattern searching?


Log in to reply
 

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