Note:
You may assume that all words are consist of lowercase letters a-z.
解题要点：
用trie来存每个字符节点。以下大神解法！
class WordDictionary(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = {}
def addWord(self, word):
"""
Adds a word into the data structure.
:type word: str
:rtype: None
"""
node = self.root
for char in word:
node = node.setdefault(char, {})
node[None] = None
def search(self, word):
"""
Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
:type word: str
:rtype: bool
"""
def find(word, root):
if not word:
return None in root
c, w = word[0], word[1:]
if c != ".":
return c in root and find(w, root[c])
return any(find(w, k) for k in root.values() if k)
return find(word, self.root)
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)