LeetCode 211. Design Ad and Search Words Data Structure - Time Limit Exceeded
JasonLaw 2022-09-30 08:54:33 +08:00 2050 次点击这是一个创建于 1138 天前的主题，其中的信息可能已经有所发展或是发生改变。
我正在解决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 PRO 之前写的题解，供参考，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