V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
JasonLaw
V2EX  ›  程序员

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

  •  
  •   JasonLaw · 2022-09-30 08:54:33 +08:00 · 1413 次点击
    这是一个创建于 545 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    结果:

    windliang
        1
    windliang  
       2022-09-30 09:39:42 +08:00
    之前写的题解,供参考,https://leetcode.wang/leetcode-211-Add-And-Search-Word-Data-structure-design.html
    xf5464
        2
    xf5464  
       2022-09-30 12:05:48 +08:00
    TreeNode 的 children 类型改为 []试一下,访问数据的下标是 element - 'a'
    Bridan
        3
    Bridan  
       2022-09-30 14:13:12 +08:00
    JasonLaw
        4
    JasonLaw  
    OP
       2022-09-30 15:13:09 +08:00
    @windliang #1
    @Bridan #3
    看了你们两的解决方法,其实想法基本都是都是跟我差不多的。

    @windliang #1
    @xf5464 #2
    @Bridan #3
    我做了一个小小的改动,修改了 base case ,现在是有时能通过,有时不能通过,应该是 LeetCode 的问题,我在提问之前也看到有人这么说。不过在我修改之前,都是通过不了的。详情请看附言。
    Bridan
        5
    Bridan  
       2022-09-30 20:39:59 +08:00
    @JasonLaw 兄弟,你用别的语言试试你的思路,可能就没问题了
    JasonLaw
        6
    JasonLaw  
    OP
       2022-09-30 21:05:00 +08:00
    @Bridan #5 嗯,Python 的确不是特别快,不过我不在意速度,只要思路对就 OK 了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3718 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 10:39 · PVG 18:39 · LAX 03:39 · JFK 06:39
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.