LeetCode 211. Design Add and Search Words Data Structure - Time Limit Exceeded
JasonLaw · 2022-09-30 08:54:33 +08:00 · 1615 次点击这是一个创建于 787 天前的主题，其中的信息可能已经有所发展或是发生改变。
我正在解决Design Add and Search Words Data Structure - LeetCode，但是出现了 Time Limit Exceeded ，我应该怎么解决？哪里可以优化？
class TreeNode:
def __init__(self):
self.children = {}
self.end_of_word = False
# prefix tree
class WordDictionary:
def __init__(self):
self.root = TreeNode()
def addWord(self, word: str) -> None:
current = self.root
for c in word:
if c not in current.children:
current.children[c] = TreeNode()
current = current.children[c]
current.end_of_word = True
def search(self, word: str) -> bool:
# search using recursion
def _search(i, current):
if i == len(word) - 1:
if word[i] == '.':
for child in current.children.values():
if child.end_of_word:
return True
return False
elif word[i] in current.children:
return current.children[word[i]].end_of_word
else:
return False
if word[i] == '.':
for child in current.children.values():
if _search(i + 1, child):
return True
return False
elif word[i] in current.children:
return _search(i + 1, current.children[word[i]])
else:
return False
return _search(0, self.root)
第 1 条附言 · 2022-09-30 15:12:16 +08:00
我做了一个小小的改动，修改了base case，现在是有时能通过，有时不能通过，应该是LeetCode的问题，我在提问之前也看到有人这么说。
下面的comment来源于Design Add and Search Words Data Structure - Leetcode 211 - Python - YouTube
我所做的改变是：
# before
if i == len(word) - 1:
if word[i] == '.':
for child in current.children.values():
if child.end_of_word:
return True
return False
elif word[i] in current.children:
return current.children[word[i]].end_of_word
else:
return False
# after
if i == len(word):
return current.end_of_word
结果：
 |
1
windliang 2022-09-30 09:39:42 +08:00
之前写的题解，供参考，https://leetcode.wang/leetcode-211-Add-And-Search-Word-Data-structure-design.html
|
 |
2
xf5464 2022-09-30 12:05:48 +08:00
TreeNode 的 children 类型改为 []试一下，访问数据的下标是 element - 'a'
|
 |
3
Bridan 2022-09-30 14:13:12 +08:00
|
 |
4
JasonLaw OP |
Select Language