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.

For example:

addWord("bad")

addWord("dad")

addWord("mad")

search("pad") -> false

search("bad") -> true

search(".ad") -> true

search("b..") -> true

代码：

定义字典树Trie节点

实现的add和search

search方法

解题思路：大致和构建字典树trie的思路一样，利用字典树对单词进行查找和插入。不同的是在查找word时，遇见了 ' .  ' 要特殊处理，需要跳过当前节点p，遍历p的儿子节点（next），进行递归判断。

全文引用自：leetcode 解释的很清楚