这个 trie 实现有什么问题吗

这个 trie 实现有什么问题吗,第1张

这个 trie 实现有什么问题吗,第2张

leetcode208 很简单的 trie 实现,下面这个 case 在 debug 的时候都是结果是[null, false],但是 submit 之后结果就变成了[null,true],是哪部分代码触发了服务器的异常编译吗?

class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word: str) -> None:
        ptr = self.root
        for ch in word:
            if ch not in ptr.child:
                ptr.child[ch] = Node("")
            if ch == word[-1]:
                ptr.child[ch].val = ch
                return
            ptr = ptr.child[ch]

    def search(self, word: str) -> bool:
        ptr = self.root
        for ch in word:
            if ch not in ptr.child:
                return False
            ptr = ptr.child[ch]
        return ptr.val == word[-1]

    def startsWith(self, prefix: str) -> bool:
        ptr = self.root
        for ch in prefix:
            if ch not in ptr.child:
                return False
            ptr = ptr.child[ch]
        return True
    
class Node:
    def __init__(self, val="", child={}):
        self.child = child
        self.val = val


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Input:

["Trie","startsWith"]
[[],["a"]]

Output:

[null,true]

Expect:

[null,false]
----------------------- 以下是精选回复-----------------------

答:insert 里逻辑不对。第二个 if 是干啥的,错的很离谱
答:bug 不止一个。你说的问题是因为:

```python
class Node:
def __init__(self, c={}):
self.c = c

n1 = Node()
n2 = Node()
n1.c is n2.c # True
```

DABAN RP主题是一个优秀的主题,极致后台体验,无插件,集成会员系统
网站模板库 » 这个 trie 实现有什么问题吗

0条评论

发表评论

提供最优质的资源集合

立即查看 了解详情