C++ clear trie tree and recursion :)


  • 0
    A
    struct Node{
        char ch;
        map<char, Node*> child;
        Node(char ch){this->ch = ch;}
        Node(){ch = 0;}
    };
    
    Node* root;
    WordDictionary() {
        root = new Node();
    }
    
    void addWord(string word) {
        Node* node = root;
        for(auto item : word){
            if(node->child.count(item) == 0)node->child[item] = new Node(item);
            node = node->child[item];
        }
        node->ch = 0;
    }
    
    bool search(string word) {
        return search(root,word);
    }
    
    bool search(Node* node, string word) {
        for(int i = 0; i<word.size();i++){
            char ch = word[i];
            if(ch == '.'){
                for(auto item:node->child){
                    if(search(item.second,word.substr(i+1))) return true;
                }
                return false;
            }else{
                if(node->child.count(ch)>0)node = node->child[ch];
                else return false;
            }
        }
        return node->ch == 0;
    }

Log in to reply
 

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