我目前正在try 解决leetcode上的问题Add and Search Words Data Structure.问题如下:
设计一个支持添加新词和查找if的数据 struct 字符串与以前添加的任何字符串匹配.
实现WordDictionary类:
WordDictionary()用于初始化对象.
void addWord(word)将word添加到数据 struct 中，稍后可以进行匹配.如果数据 struct 中有任何匹配的字符串，则
bool search(word)返回trueword或false，否则.单词可以包含点.，其中点可以 与任何字母都匹配.
My Strategy:个
我的策略包括用哈希图表示Trie，而不是传统的基于链表的树 struct ，旨在提高性能和降低复杂性.通过使用哈希图，我们可以快速访问下一个 node ，而无需遍历不必要的 node ，从而使操作速度更快，尤其是在处理大型数据集时.
例如，在这种 struct 中插入苹果和应用程序等词时，它被组织为嵌套的哈希图，其中一个词中的每个字符指向代表下一个字符的另一个哈希图.单词的末尾使用特殊的键值对{‘end’:{}}进行标记.这样，我们以最小的空间和时间复杂度高效地存储和搜索单词.
My Code:个
class WordDictionary(object):
def __init__(self):
self.map = {}
def addWord(self, word):
"""
:type word: str
:rtype: None
"""
current = self.map
for i in word:
if i in current:
current = current[i]
else:
current[i] = {}
current = current[i]
current['end'] = {}
return
def search(self, word):
"""
:type word: str
:rtype: bool
"""
current = self.map
for i in word:
if i in current:
current = current[i]
elif i == '.':
current = {key: value for d in current.values() for key, value in d.items()}
else:
return False
if 'end' in current:
return True
return False
该解决方案似乎对大多数情况都有效，但我遇到了test case 16的错误，它没有给出正确的结果.测试用例16的长度使得确定错误发生在哪里特别具有挑战性.我需要一些指导来追踪fix this logical error号公路.你能帮忙解决这件事吗？