C++ implement with map


  • 0
    S
    class Node {
    public:
        bool isword;
        map<char, Node*> nodes;
        Node() { isword = false; }
        ~Node() {
            for(map<char, Node*>::iterator it=nodes.begin(); it!=nodes.end(); it++)
                delete it->second;
        }
    };
    
    class WordDictionary {
    public:
        Node* root;
    
        WordDictionary() {
            root = new Node();
        }
        
        ~WordDictionary() {
            delete root;
        }
        
        // Adds a word into the data structure.
        void addWord(string word) {
            Node* node = root;
            Node* new_node = NULL;
            for(int i=0; i<word.length(); i++)
            {
                if(node->nodes[word[i]] == NULL)
                    node->nodes[word[i]] = new Node();
                node = node->nodes[word[i]];
                if(i == (word.length()-1))
                    node->isword = 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 subsearch(root, word, 0);
        }
        
        bool subsearch(Node* node, string word, int ind) {
            if(node == NULL) return false;
            if(node->isword == true && ind == word.length()) return true;
            if(ind == word.length()) return false;
    
            if(word[ind] == '.')
            {
                for(map<char, Node*>::iterator it=node->nodes.begin(); it!= node->nodes.end(); it++)
                {
                    if(subsearch(it->second, word, ind+1)) return true;
                }
            }
            else
                return subsearch(node->nodes[word[ind]], word, ind+1);
            
            return false;
        }
    };

Log in to reply
 

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