首页 > 代码库 > 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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。