这个 trie 实现有什么问题吗
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
```
0条评论