LeetCode 211. 添加与搜索单词 - 数据结构设计

LeetCode 211. 添加与搜索单词 - 数据结构设计

思路：

dfs,search的时候遇到点就依次枚举每个son。

代码：

struct Node{
    bool end;
    Node* son[26];
    Node(){
        end = false;
        for(int i = 0;i < 26;i++){
            son[i] = nullptr;
        }
    }
}*root;

class WordDictionary {
public:
    WordDictionary() {
        root = new Node();
    }
    
    void addWord(string word) {
        auto p = root;
        for(auto &w : word){
            int t = w - 'a';
            if(!p->son[t]) p->son[t] = new Node();
            p = p->son[t];
        }
        p->end = true;
    }
    
    bool search(string word) {
        return dfs(word,0,root);
    }

    bool dfs(string &word,int u,Node* root){
        if(u == word.size()) return root->end;
        if(word[u] == '.'){
            for(int i = 0;i < 26;i++){
                if(root->son[i]){
                    if(dfs(word,u + 1,root->son[i])) return true;
                }
            }
        }
        else{
            int t = word[u] - 'a';
            if(root->son[t]) return dfs(word,u + 1,root->son[t]);
        }
        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);
 */