字典树 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)