本文最后更新于 195 天前,如有失效请评论区留言。
字典树 https://leetcode.cn/problems/implement-trie-prefix-tree/description/
# 定义Trie节点类
class TrieNode:
__slots__ = 'children', 'is_end_of_word'
def __init__(self):
# 使用defaultdict存储子节点
self.children = defaultdict(TrieNode)
# 标记是否是单词结尾
self.is_end_of_word = False
# 定义Trie树类
class Trie:
__slots__ = 'root'
def __init__(self):
# 初始化根节点
self.root = TrieNode()
# 插入单词
def insert(self, word):
node = self.root
for char in word:
# 逐字符插入到Trie中
node = node.children[char]
# 标记单词结尾
node.is_end_of_word = True
# 查找单词是否存在于Trie中
def search(self, word):
node = self.search_prefix(word)
# 检查找到的节点是否是单词的结尾
return node is not None and node.is_end_of_word
# 查找是否有单词以给定前缀开始
def startsWith(self, prefix):
# 查找前缀对应的节点
return self.search_prefix(prefix) is not None
# 辅助函数,用于查找前缀
def search_prefix(self, prefix):
node = self.root
for char in prefix:
# 如果字符不在当前节点的子节点中,返回None
if char not in node.children:
return None
# 继续查找下一个字符
node = node.children[char]
# 返回找到的节点
return node
# 返回Trie树中与给定单词具有最长公共前缀的词根,如果找不到则返回空字符串。
def get_longest_prefix(self, word: str) -> str:
node = self.root
longest_prefix = []
for char in word:
if char in node.children:
longest_prefix.append(char)
node = node.children[char]
if node.is_end_of_word:
return ''.join(longest_prefix)
else:
break
return ""
# 删除一个单词,如果删除成功返回 True,否则返回 False
def delete(self, word: str) -> None:
def _delete(node, word, depth):
if depth == len(word):
if node.is_end_of_word:
node.is_end_of_word = False
return not bool(node.children)
char = word[depth]
if char in node.children and _delete(node.children[char], word, depth + 1):
del node.children[char]
return not bool(node.children) and not node.is_end_of_word
return False
_delete(self.root, word, 0)
简单入门题:https://leetcode.cn/problems/replace-words/description/
# 定义Trie节点类
class TrieNode:
__slots__ = 'children', 'is_end_of_word'
def __init__(self):
# 使用defaultdict存储子节点
self.children = defaultdict(TrieNode)
# 标记是否是单词结尾
self.is_end_of_word = False
# 定义Trie树类
class Trie:
__slots__ = 'root'
def __init__(self):
# 初始化根节点
self.root = TrieNode()
# 插入单词
def insert(self, word):
node = self.root
for char in word:
# 逐字符插入到Trie中
node = node.children[char]
# 标记单词结尾
node.is_end_of_word = True
# 查找单词是否存在于Trie中
def search(self, word):
node = self.search_prefix(word)
# 检查找到的节点是否是单词的结尾
return node is not None and node.is_end_of_word
# 查找是否有单词以给定前缀开始
def startsWith(self, prefix):
# 查找前缀对应的节点
return self.search_prefix(prefix) is not None
# 辅助函数,用于查找前缀
def search_prefix(self, prefix):
node = self.root
for char in prefix:
# 如果字符不在当前节点的子节点中,返回None
if char not in node.children:
return None
# 继续查找下一个字符
node = node.children[char]
# 返回找到的节点
return node
def get_longest_prefix(self, word: str) -> str:
"""
返回Trie树中与给定单词具有最长公共前缀的词根。
Args:
- word: 待查找的单词
Returns:
- str: 最长公共前缀的词根,如果找不到则返回空字符串。
"""
node = self.root
longest_prefix = []
for char in word:
if char in node.children:
longest_prefix.append(char)
node = node.children[char]
if node.is_end_of_word:
return ''.join(longest_prefix)
else:
break
return ""
class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
sentence_words = sentence.split()
tree = Trie()
# 构建Trie树
for word in dictionary:
tree.insert(word)
# 替换单词
for i in range(len(sentence_words)):
word = sentence_words[i]
root = tree.get_longest_prefix(word)
if root:
sentence_words[i] = root
return ' '.join(sentence_words)