[数据结构与算法]力扣-211题 添加与搜索单词 - 数据结构设计（C++）- dfs+字典树+有价值

题目链接：https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/
题目如下：

class WordDictionary {
public:
    struct Node{
        Node* son[26];
        bool is_end;
        Node(){
            for(int i=0;i<26;i++)
                son[i]=NULL;
            is_end=false;
        }
    }*root;

    WordDictionary() {
        root=new Node();
    }
    
    void addWord(string word) {
        auto p=root;
        for(char ch:word){
            int pos=ch-'a';
            if(p->son[pos]==NULL) p->son[pos]=new Node();
            p=p->son[pos];    
        }
        p->is_end=true;
    }
    
    bool search(string word) {
        return dfs(root,word,0);
    }

    bool dfs(Node* root,string& word,int start){
        if(start==word.size()) return root->is_end;

        if(word[start]!='.'){
            int pos=word[start]-'a';
            if(root->son[pos]==NULL) return false;
            return dfs(root->son[pos],word,start+1);
        }else{
            for(int i=0;i<26;i++){
                if(root->son[i]&&dfs(root->son[i],word,start+1)) return true;                
            }
            return false;
        }
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */