211. Add and Search Word - Data structure design(难啊)
程序员文章站
2022-05-18 10:03:14
...
题目
一个简单的添加单词,返回查找是否存在的数据结构。
我的代码(超时)
class WordDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.words=set()
def addWord(self, word: str) -> None:
"""
Adds a word into the data structure.
"""
self.words.add(word)
def search(self, word: str) -> bool:
"""
Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
"""
for s in self.words:
if re.match(word+'$', s, flags=0):
return True
return False
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)
讨论区代码(效率中等/但方法很神奇)
初始版本:
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word):
node = self.root
for char in word:
node = node.setdefault(char, {})
node[None] = None
# 一个容易理解的search
def search(self, word):
def find(word, node):
if not word:
return None in node
char, word = word[0], word[1:]
if char != '.':
return char in node and find(word, node[char])
return any(find(word, kid) for kid in node.values() if kid)
两种search:
def search(self, word):
nodes = [self.root]
for char in word:
nodes = [kid
for node in nodes
for key, kid in node.items()
if char in (key, '.') and kid]
return any(None in node for node in nodes)
And one that's a bit longer but faster:
def search(self, word):
nodes = [self.root]
for char in word:
nodes = [kid for node in nodes for kid in
([node[char]] if char in node else
filter(None, node.values()) if char == '.' else [])]
return any(None in node for node in nodes)
最后的简洁版本:
class WordDictionary:
def __init__(self):
self.root = {}
# 添加了一个树状的字典
def addWord(self, word):
node = self.root
for char in word:
node = node.setdefault(char, {})
node['$'] = None
print(self.root)
# 逐层查询结果
def search(self, word):
nodes = [self.root]
for char in word + '$':
nodes = [kid for node in nodes for kid in
([node[char]] if char in node else
filter(None, node.values()) if char == '.' else [])]
return bool(nodes)
高效代码
class WordDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.dic = collections.defaultdict(list)
def addWord(self, word: 'str') -> 'None':
"""
Adds a word into the data structure.
"""
# 根据长度来分类单词
if word:
self.dic[len(word)].append(word)
def search(self, word: 'str') -> 'bool':
"""
Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
"""
# 如果没有. 符号就简单了
if "." not in word:
return word in self.dic[len(word)]
# 如果有.就需要逐个字符判断。
for word2 in self.dic[len(word)]:
for i, c1 in enumerate(word):
if c1 != "." and word2[i] != c1:
break
else:
return True
return False
推荐阅读
-
【leetcode】211. Add and Search Word - Data structure design
-
LeetCode-211. Add and Search Word - Data structure design(字典树和递归)
-
【Leetcode&C语言&Tire】208.Implement Trie (Prefix Tree) & 211.Design Add and Search Words Data Structure
-
211. Add and Search Word - Data structure design(难啊)
-
Add and Search Word - Data structure design