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

[Animenzzzz]

题目描述：

设计一个支持以下两种操作的数据结构：

void addWord(word)
bool search(word)

search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。

示例:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

说明:

你可以假设所有单词都是由小写字母 a-z 组成的。

解题思路：这题是常规的字典树，唯一不同的是需要匹配正则表达式。其他的初始化操作都一样，在搜索时需要修改。参考的 grandyang/leetcode#211
当遇到 . 时，需要匹配下一个字符，跳过 . 。自己做的时候，第一个条件写成了 if(p && p->isWordEnd && index == word.size()) return true; 总报树的child越界。。。蛋疼。。。

C++解题：

class TrieNode{
public:
    TrieNode *child[26];
    bool isWordEnd;
    TrieNode():isWordEnd(false){
        for (int i = 0; i < 26; i++) child[i] = nullptr;
    }
};
class WordDictionary {
public:

    WordDictionary() {
        
    }
    
    void addWord(string word) {
        TrieNode *p = root;
        for(char cc:word){
            int index = cc - 'a';
            if(!p->child[index]) p->child[index] = new TrieNode();
            p = p->child[index];
        }
        p->isWordEnd = true;
    }
    
    bool search(string word) {
        return searchWord(word,0,root);
    }

    bool searchWord(string &word,int index,TrieNode *p){
        if(index == word.size()) return p->isWordEnd;
        if(word[index] == '.'){
            for (auto &a : p->child) {
                if (a && searchWord(word, index + 1,a)) return true;
            }
            return false;
        }else{
            return p->child[word[index] - 'a'] && searchWord(word, index + 1,p->child[word[index] - 'a']);
        }
    }
private:
    TrieNode *root = new TrieNode();
};