【LeetCode每日一题】211. 添加与搜索单词 - 数据结构设计 【中等】字典树+dfs

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

实现词典类 WordDictionary ：

WordDictionary() 初始化词典对象 void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配 bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。  

示例：

输入： ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] 输出： [null,null,null,null,false,true,true,true]

解释： WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True  

提示：

1 <= word.length <= 500 addWord 中的 word 由小写英文字母组成 search 中的 word 由 '.' 或小写英文字母组成 最多调用 50000 次 addWord 和 search

题解： 当时看到这道题的时候就觉得应该是用字典树的方式，但是对于字典树怎么定义的细节有点不太记得了。直接暴力有很大的几率会超时。这道题可以将.看作对26个小写字母的匹配，其他的就按照模板来就好了。

class WordDictionary {
public:
    struct TrieNode{
        vector<TrieNode*> child;
        bool isEnd;
        TrieNode(){
            this -> child = vector<TrieNode*> (26, NULL);
            this -> isEnd = false;
        }
    };

    void insert(TrieNode* root, string word){
        TrieNode* node = root;
        for(auto ch: word){
            if(node -> child[ch - 'a']){
                node = node -> child[ch - 'a'];
            }
            else{
                node -> child[ch - 'a'] = new TrieNode();
                node = node -> child[ch - 'a'];
            };
        }
        node -> isEnd = true;

        // TrieNode * node = root;
        // for (auto c : word) {
        //     if (node->child[c - 'a'] == nullptr) {
        //         node->child[c - 'a'] = new TrieNode();
        //     }
        //     node = node->child[c - 'a'];
        // }
        // node->isEnd = true;


    }

    TrieNode* trie;

    WordDictionary() {
        trie = new TrieNode();
    }
    
    void addWord(string word) {
        insert(trie, word);
    }
    
    bool search(string word) {
        return dfs(word, 0, trie);
    }

    bool dfs(string word, int pos, TrieNode* node){
        if(pos == word.size()){
            return node -> isEnd;
        }
        if(word[pos] == '.'){
            for(int i = 0; i < 26; i++){
                if(node -> child[i] != NULL && dfs(word, pos + 1, node -> child[i])){
                    return true;
                }
            }
        }
        else if(word[pos] >= 'a' && word[pos] <= 'z'){
            if(node -> child[word[pos] - 'a'] && dfs(word, pos + 1, node -> child[word[pos] - 'a'])){
                return true;
            }
        }
        return false;



        // if (index == word.size()) {
        //     return node->isEnd;    
        // }
        // char ch = word[index];
        // if (ch >= 'a' && ch <= 'z') {
        //     TrieNode * child = node->child[ch - 'a'];
        //     if (child != nullptr && dfs(word, index + 1, child)) {
        //         return true;
        //     }
        // } else if (ch == '.') {
        //     for (int i = 0; i < 26; i++) {
        //         TrieNode * child = node->child[i];
        //         if (child != nullptr && dfs(word, index + 1, child)) {
        //             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);
 */