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

野性酷女 2022-09-16 12:25 103阅读 0赞

题目链接：[https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/][https_leetcode-cn.com_problems_design-add-and-search-words-data-structure]  
题目如下：  
![在这里插入图片描述][d8130a1b7e3a4c918a3b021145bfeccd.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]

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);
     */

[https_leetcode-cn.com_problems_design-add-and-search-words-data-structure]: https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/
[d8130a1b7e3a4c918a3b021145bfeccd.png]: /images/20220828/94ceea7976e84d22bd503a41dc8bb672.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/36338893af484d83a3179ea9fe9b084b.png