leetcode_字典树 208. 实现 Trie (前缀树)

• Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

• 请你实现 Trie 类：

• Trie() 初始化前缀树对象。
  void insert(String word) 向前缀树中插入字符串 word 。
  boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

• 示例：

• 输入
  [“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]

  [ [], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”] ]

• 输出

  [null, null, true, false, true, null, true]

• 解释
  Trie trie = new Trie();

  trie.insert(“apple”);

  trie.search(“apple”); // 返回 True

  trie.search(“app”); // 返回 False

  trie.startsWith(“app”); // 返回 True

  trie.insert(“app”);

  trie.search(“app”); // 返回 True

1. 理解

• Trie是一种树形结构，用来存储字符串，每一个节点代表一个字符串（前缀）。每一个节点会有多个子节点，通往不同子节点的路径上有着不同的字符。子节点代表的字符串是由节点本身的原始字符串，以及通往该子节点路径上所有的字符组成的。

2. 构造

字典实现前缀树的核心思想

1. 节点结构：

• 每个节点是一个字典（dict），键是字符，值是对应的子节点。

• 每个节点还需要一个标志 is_end_of_word，用于标记当前节点是否是一个单词的结尾。

2. 插入操作：

• 从根节点开始，逐字符检查并创建子节点。

• 如果字符不存在于当前节点的字典中，则创建一个新的子节点。

• 插入完成后，在最后一个字符的节点上标记 is_end_of_word = True。

3. 搜索操作：

• 从根节点开始，逐字符检查是否存在对应的子节点。

• 如果路径存在且最后一个节点的 is_end_of_word 为 True，则返回 True，否则返回 False。

4. 前缀匹配操作：

• 从根节点开始，逐字符检查是否存在对应的子节点。

• 如果路径存在，则返回 True，否则返回 False。

3. 实现

class TrieNode:
    def __init__(self):
        self.children = {}  # 存储子节点
        self.is_end_of_word = False  # 标记是否为单词的结尾

class Trie(object):

    def __init__(self):
        self.root = TrieNode()  # 初始化根节点

    def insert(self, word):
        """
        :type word: str
        :rtype: None
        """
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()  # 如果字符不存在，创建新节点
            node = node.children[char]  # 移动到子节点
        node.is_end_of_word = True  # 标记单词结束
        

    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        node = self.root
        for char in word:
            if char not in node.children:
                return False  # 如果字符不存在，返回 False
            node = node.children[char]  # 移动到子节点
        return node.is_end_of_word  # 检查是否是单词的结尾
        

    def startsWith(self, prefix):
        """
        :type prefix: str
        :rtype: bool
        """
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False  # 如果字符不存在，返回 False
            node = node.children[char]  # 移动到子节点
        return True  # 前缀存在，返回 True

4. 时间复杂度

• 插入：O(n)，其中 n 是单词的长度。

• 搜索和前缀匹配：O(n)，其中 n 是单词或前缀的长度。