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

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

  •  
  •   JasonLaw · 62 天前 · 845 次点击
    这是一个创建于 62 天前的主题,其中的信息可能已经有所发展或是发生改变。

    我正在解决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 条附言  ·  62 天前

    我做了一个小小的改动,修改了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  
       62 天前
    之前写的题解,供参考,https://leetcode.wang/leetcode-211-Add-And-Search-Word-Data-structure-design.html
    xf5464
        2
    xf5464  
       62 天前
    TreeNode 的 children 类型改为 []试一下,访问数据的下标是 element - 'a'
    Bridan
        3
    Bridan  
       62 天前
    JasonLaw
        4
    JasonLaw  
    OP
       62 天前
    @windliang #1
    @Bridan #3
    看了你们两的解决方法,其实想法基本都是都是跟我差不多的。

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