Add and Search Word - Data Structure Design

此题是Trie树和回溯结合的应用类题目，主要注意的是DFS时候的出口条件，找到这个词的条件是词指针到底且当前trie树结点有休止符存在，而且只要指针到底就必须返回不能再递归了

class WordDictionary(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trieNode = {}

    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        cur = self.trieNode
        for char in word:
            cur.setdefault(char, {})
            cur = cur[char]
        cur['#'] = {}

    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
        """
        cur = self.trieNode
        return self._helper(word, 0, len(word), cur)

    def _helper(self, word, start, end, checker):
        if start == end:
            if '#' in checker:
                return True
            return False

        if word[start] == '.':
            for char in checker.keys():
                if self._helper(word, start + 1, end, checker[char]):
                    return True

        if word[start] in checker:
            return self._helper(word, start + 1, end, checker[word[start]])

        return False


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)