Sharing my 152ms C++ solution


  • 0
    T
    // build the WordDictionary using trie data structure
    class TrieNode
    {
    private:
        char nContent;
        bool nMarker;
        vector<TrieNode*> nChildren;
    
    public:
        TrieNode()
        {
            nContent = ' ';
            nMarker = false;
            nChildren.resize(0);
        }
        
        ~TrieNode(){}
        
        char content()
        {
            return nContent;
        }
        
        void setContent(char c)
        {
            nContent = c;
        }
        
        bool wordMarker()
        {
            return nMarker;
        }
        
        void setWordMarker()
        {
            nMarker = true;
        }
        
        TrieNode* findChild(char c)
        {
            for(int i=0; i<nChildren.size(); i++)
            {
                if(c == nChildren[i]->content())
                    return nChildren[i];
            }
            
            return NULL;
        }
        
        void addChild(TrieNode* child)
        {
            nChildren.push_back(child);
        }
        
        vector<TrieNode*> children()
        {
            return nChildren;
        }
    };
    
    class WordDictionary {
    private:
        TrieNode* root;
    public:
        WordDictionary()
        {
            root = new TrieNode();
        }
        
        // Adds a word into the data structure.
        void addWord(string word) {
            int n = word.length();
            if(n==0)
            {
                root->setWordMarker();
                return;
            }
            
            int i;
            TrieNode* current = root;
            for(i=0; i<n; i++)
            {
                TrieNode* child = current->findChild(word[i]);
                if(child)
                    current = child;
                else
                {
                    child = new TrieNode();
                    child->setContent(word[i]);
                    current->addChild(child);
                    current = child;
                }
                if(i==word.length()-1)
                    current->setWordMarker();
            }
        
        }
    
        // Returns if the word is in the data structure. A word could
        // contain the dot character '.' to represent any one letter.
        bool searchHelper(TrieNode* node, string word, int depth)
        {
            if(depth == word.length())
                return node->wordMarker();
                
            if(word[depth] == '.')
            {
                vector<TrieNode*> mChildren = node->children();;
                for(int i=0; i<mChildren.size(); i++)
                    if(searchHelper(mChildren[i], word, depth+1))
                        return true;
                        
                return false;
            }
            else
            {
                TrieNode* child = node->findChild(word[depth]);
                if(child == NULL)
                    return false;
                else
                    return searchHelper(child, word, depth+1);
            }
        }
        
        bool search(string word) {
            return searchHelper(root, word, 0);
        }
    };
    
    // Your WordDictionary object will be instantiated and called as such:
    // WordDictionary wordDictionary;
    // wordDictionary.addWord("word");
    // wordDictionary.search("pattern");

Log in to reply
 

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