题目描述

请设计一个数据结构，需要满足如下两种操作：

void addWord(word)
bool search(word)

search(word) 可以查找一个正则表达式，正则表达式只包含a-z和.，.可以匹配任意字母。

注意： 数据保证所有单词均只包含小写字母a-z。

样例

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

算法

(trie树) $add: O(L), search: O(nL)$

我们可以用trie树来保存所有单词。
trie树也叫字典树，如下所示，该树中存储了
"at", "bee", "ben", "bt", "q"这几个单词。

因为插入的单词不包含通配符.，所以我们可以直接插入。
难点在于如何查找包含通配符的单词。我们可以用DFS搜索：

1. 当遇到字母a-z时，直接进入trie树节点对应的儿子；
2. 当遇到通配符.时，枚举当前trie树节点的所有儿子；

时间复杂度分析：假设单词的平均长度是 $L$，总共有 $n$ 个单词。add操作会遍历 $L$ 个节点，所以时间复杂度是 $O(L)$；search操作最坏情况下会遍历所有节点，所以时间复杂度是 $O(nL)$。

C++ 代码

class WordDictionary {
public:
    struct Node
    {
        bool is_end;
        Node *next[26];
        Node()
        {
            is_end = false;
            for (int i = 0; i < 26; i ++ )
                next[i] = 0;
        }
    };

    Node *root;

    /** Initialize your data structure here. */
    WordDictionary() {
        root = new Node();
    }

    /** Adds a word into the data structure. */
    void addWord(string word) {
        Node *p = root;
        for (char c : word)
        {
            int son = c - 'a';
            if (!p->next[son]) p->next[son] = new Node();
            p = p->next[son];
        }
        p->is_end = true;
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        return dfs(word, 0, root);
    }

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