首页 > 代码库 > LeetCode 211. Add and Search Word - Data structure design

LeetCode 211. Add and Search Word - Data structure design

原题

设计一个包含下面两个操作的数据结构:addWord(word), search(word)
addWord(word)会在数据结构中添加一个单词。而search(word)则支持普通的单词查询或是只包含. 和a-z的简易正则表达式的查询。一个 . 可以代表一个任何的字母。

样例

addWord("bad")addWord("dad")addWord("mad")search("pad")  // return falsesearch("bad")  // return truesearch(".ad")  // return truesearch("b..")  // return true

解题思路

  • 本题跟Implement Trie十分相似,同样需要使用字典树
  • 由于本题里中‘.‘可以代替任意字符,所以当某一个字符是‘.‘,就需要查找所有的子树,只要有一个最终能够存在,就返回True
  • 一个字母一个字母的递归

完整代码

class TrieNode(object):        def __init__(self):                self.child = {}        self.isword = Falseclass WordDictionary(object):    def __init__(self):        """        Initialize your data structure here.        """        self.root = TrieNode()            def addWord(self, word):        """        Adds a word into the data structure.        :type word: str        :rtype: void        """        node = self.root        for i in word:            if not node.child.get(i):                node.child[i] = TrieNode()            node = node.child[i]        node.isword = 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        """        return self.find(self.root, word)            def find(self, node, word):        if word == "":            return node.isword        if word[0] == ‘.‘:            for key in node.child:                if self.find(node.child.get(key), word[1:]):                    return True        else:            if not node.child.get(word[0]):                return False            return self.find(node.child.get(word[0]),word[1:])        return False    #防止44行里面的节点后面没有key值或是返回false# Your WordDictionary object will be instantiated and called as such:# obj = WordDictionary()# obj.addWord(word)# param_2 = obj.search(word)

  

LeetCode 211. Add and Search Word - Data structure design