题目描述

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

样例

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

算法1

(Trie) $O(m)$

建Trie，完成add和search function。输入字符是’.’时，当前node不为空且递归调用后为true时返回true

时间复杂度

m为字符长度

参考文献

C++ 代码

class TrieNode
{
public:
    bool end;
    TrieNode* children[26];
    TrieNode():end(false){
        for(auto &ch:children)
            ch=NULL;
    }
};
class WordDictionary {
public:
    /** Initialize your data structure here. */
    WordDictionary() {

    }
    void addWord(string word)
    {
        TrieNode* node=root;
        for(char c:word)
        {
            if(!node->children[c-'a'])
                node->children[c-'a']=new TrieNode();
            node=node->children[c-'a'];
        }
        node->end=true;
    }

    bool search(string word)
    {
        return searchWord(word, root, 0);
    }    

private:
    TrieNode* root = new TrieNode();

    bool searchWord(string word, TrieNode* p, int i)
    {
        if(i==word.size()) return p->end;
        if(word[i]=='.')
        {
            for(auto &a: p->children)
            {
                if(a && searchWord(word, a, i+1)) return true;                
            }
            return false;
        }
        else
            return p->children[word[i]-'a'] && searchWord(word, p->children[word[i]-'a'], i+1);
    }

};

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

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla