字典树模板
本文最后更新于 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)
版权声明:除特殊说明,博客文章均为大块肌原创,依据CC BY-SA 4.0许可证进行授权,转载请附上出处链接及本声明。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇