难度: Medium
Submission
运行时间: 177 ms
内存: 28.9 MB
class Trie:
def __init__(self):
self.children = {}
self.count = 0
self.endCount = 0
def insert(self, word: str) -> None:
node = self
for w in word:
if w not in node.children:
node.children[w] = Trie()
node = node.children[w]
node.count += 1
node.endCount += 1
def countWordsEqualTo(self, word: str) -> int:
node = self
for w in word:
if w not in node.children:
return 0
node = node.children[w]
return node.endCount
def countWordsStartingWith(self, prefix: str) -> int:
node = self
for w in prefix:
if w not in node.children:
return 0
node = node.children[w]
return node.count
def erase(self, word: str) -> None:
node = self
for w in word:
node = node.children[w]
node.count -= 1
node.endCount -= 1
Explain
这个题解实现了一个 Trie (前缀树) 数据结构，并支持插入、查询和删除字符串的操作。每个节点包含一个映射表 children 来保存子节点，一个 count 变量记录经过此节点的单词数量，和一个 endCount 变量记录以此节点结尾的单词数量。在 insert 方法中，遍历插入的单词的每个字符，如果字符不存在于当前节点的 children 中，则创建一个新的 Trie 节点。同时更新经过的每个节点的 count 值。countWordsEqualTo 方法通过遍历单词找到对应的节点并返回其 endCount 值，表示完全匹配该单词的数量。countWordsStartingWith 方法遍历前缀找到对应节点并返回其 count 值，表示以该前缀开始的单词数量。erase 方法用于删除一个单词，它减少经过每个节点的 count 值和最终节点的 endCount 值。
时间复杂度: O(m)
空间复杂度: O(∑w)
class Trie:
def __init__(self):
self.children = {} # 存储子节点的字典
self.count = 0 # 经过此节点的单词数量
self.endCount = 0 # 以此节点结尾的单词数量
def insert(self, word: str) -> None:
node = self
for w in word:
if w not in node.children:
node.children[w] = Trie() # 创建新的 Trie 节点
node = node.children[w]
node.count += 1 # 更新经过节点的计数
node.endCount += 1 # 更新结束节点的计数
def countWordsEqualTo(self, word: str) -> int:
node = self
for w in word:
if w not in node.children:
return 0
node = node.children[w]
return node.endCount # 返回完全匹配的单词数量
def countWordsStartingWith(self, prefix: str) -> int:
node = self
for w in prefix:
if w not in node.children:
return 0
node = node.children[w]
return node.count # 返回以此前缀开始的单词数量
def erase(self, word: str) -> None:
node = self
for w in word:
node = node.children[w]
node.count -= 1 # 减少经过节点的计数
node.endCount -= 1 # 减少结束节点的计数
Explore
不完全是这样。这种设计只是表明，如果在查询过程中遇到 Trie 中不存在的字符，则可以断定 Trie 中不存在以此字符为部分的完整单词。这并不意味着所有 Trie 操作都假设输入字符串完全由已知字符集构成，而是说明 Trie 对于未知字符的查询将返回 0，表示这样的单词不存在。在 Trie 的其他操作中，如插入或删除，会动态处理字符集，添加或修改 Trie 的结构。
在 Trie 中，`count` 和 `endCount` 变量确实用来跟踪经过每个节点的单词数量和以该节点结尾的单词数量。当执行删除操作时，这些值会相应减少。如果某节点的 `count` 值减少到零，理论上这意味着没有任何单词再通过这个节点。尽管如此，该节点可能仍然保留在 Trie 中，除非额外实现节点的清除逻辑。这通常涉及到检查节点是否还有子节点，以及 `endCount` 是否为零，如果没有子节点且 `endCount` 为零，则可以安全地移除该节点。没有这样的清除逻辑，即使 `count` 为零的节点也会保留在 Trie 中。