we are asked to design an efficient data structure that allows us to add and search for words the search can be a literal word or regular expression containing where can be any letter example addwordbad addworddad addwordmad searchpad false searchbad true search ad true searchb true if dot if letter match xx xx x with yyyyyyy if dot if last character if letter match xx xx x with yyyyyyy
import collections

class TrieNode(object):
    def __init__(self, letter, is_terminal=False):
        self.children = dict()
        self.letter = letter
        self.is_terminal = is_terminal

class WordDictionary(object):
    def __init__(self):
        self.root = TrieNode("")

    def add_word(self, word):
        cur = self.root
        for letter in word:
            if letter not in cur.children:
                cur.children[letter] = TrieNode(letter)
            cur = cur.children[letter]
        cur.is_terminal = True

    def search(self, word, node=None):
        cur = node
        if not cur:
            cur = self.root
        for i, letter in enumerate(word):
            
            if letter == ".":
                if i == len(word) - 1: 
                    for child in cur.children.itervalues():
                        if child.is_terminal:
                            return True
                    return False
                for child in cur.children.itervalues():
                    if self.search(word[i+1:], child) == True:
                        return True
                return False
            
            if letter not in cur.children:
                return False
            cur = cur.children[letter]
        return cur.is_terminal

class WordDictionary2(object):
    def __init__(self):
        self.word_dict = collections.defaultdict(list)


    def add_word(self, word):
        if word:
            self.word_dict[len(word)].append(word)

    def search(self, word):
        if not word:
            return False
        if '.' not in word:
            return word in self.word_dict[len(word)]
        for v in self.word_dict[len(word)]:
            
            for i, ch in enumerate(word):
                if ch != v[i] and ch != '.':
                    break
            else:
                return True
        return False