211. Add and Search Word - Data

字典树
在计算机科学中，Trie，又称字典树、单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
它有3个基本性质：
根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同。
############################################
回到这一题，创建了一种数据结构wordNode，数据结构包含一个字典，和一个bool变量，初始化一个root,为wordNode类型变量，然后遍历word将字符加入到字典树上

class wordNode():
   def __init__(self):
       self.children = {}
       self.isEnd = False
class WordDictionary(object):

   def __init__(self):
       """
       Initialize your data structure here.
       """
       self.root = wordNode()
       

   def addWord(self, word):
       """
       Adds a word into the data structure.
       :type word: str
       :rtype: void
       """
       node = self.root
       for w in word:
           if w in node.children:
               node = node.children[w]
           else:
               node.children[w] = wordNode()
               node = node.children[w]
       node.isEnd =  True
       

   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
       """
       stack = [(self.root, word)]
       while stack:
           node, w = stack.pop()
           if not w:
               if node.isEnd:
                   return True
           elif w[0] == '.':
               for v in node.children.values():
                   stack.append((v, w[1:]))
           else:
               if w[0] in node.children:
                   stack.append((node.children[w[0]], w[1:]))
       return False
                  

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

dfs的做法

class wordNode():
    def __init__(self):
        self.children = {}
        self.isEnd = False
class WordDictionary(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = wordNode()
        

    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        node = self.root
        for w in word:
            if w in node.children:
                node = node.children[w]
            else:
                node.children[w] = wordNode()
                node = node.children[w]
        node.isEnd =  True
        

    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
        """
        self.res = False
        self.dfs(self.root, word)
        return self.res
    def dfs(self, root, word):
        if not word:
            if root.isEnd:
                self.res =True
            return
        elif word[0] == '.':
            for v in root.children.values():
                self.dfs(v, word[1:])
        else:
            if word[0] in root.children:
                self.dfs(root.children[word[0]], word[1:])
                
                
            
                    
        


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