LeetCode 211. Design Add and Search Words Data Structure - Time Limit Exceeded

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 784 天前的主题，其中的信息可能已经有所发展或是发生改变。

我正在解决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

结果：

return

ildr

word

6 条回复

windliang

2022-09-30 09:39:42 +08:00

之前写的题解，供参考，https://leetcode.wang/leetcode-211-Add-And-Search-Word-Data-structure-design.html

xf5464

2022-09-30 12:05:48 +08:00

TreeNode 的 children 类型改为 []试一下，访问数据的下标是 element - 'a'

Bridan

2022-09-30 14:13:12 +08:00

看都看到了，顺手写了
https://leetcode.cn/submissions/detail/368752867/

JasonLaw

2022-09-30 15:13:09 +08:00

@windliang #1
@Bridan #3
看了你们两的解决方法，其实想法基本都是都是跟我差不多的。

@windliang #1
@xf5464 #2
@Bridan #3
我做了一个小小的改动，修改了 base case ，现在是有时能通过，有时不能通过，应该是 LeetCode 的问题，我在提问之前也看到有人这么说。不过在我修改之前，都是通过不了的。详情请看附言。

Bridan

2022-09-30 20:39:59 +08:00

@JasonLaw 兄弟，你用别的语言试试你的思路，可能就没问题了

JasonLaw

2022-09-30 21:05:00 +08:00

@Bridan #5 嗯，Python 的确不是特别快，不过我不在意速度，只要思路对就 OK 了。