Leetcode 剑指 Offer II 062. 实现 Trie (前缀树)

题目难度: 中等

原题链接

今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

请你实现 Trie 类：

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

示例：

• 输入
  • inputs = [“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
  • inputs = [[], [“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 <= word.length, prefix.length <= 2000
• word 和 prefix 仅由小写英文字母组成
• insert、search 和 startsWith 调用次数 总计 不超过 3 * 10^4 次

题目思考

1. 如何定义哪些类, 包含哪些字段?

解决方案

思路

• 这道题就是典型的 Trie 的实现, 可以参考下图:
  • 
• 从图中可以看出, 每个非叶节点指向其子节点的边上都有一个字符
• 另外有的节点标记为红色, 代表从根节点到该节点形成了一个完整的单词, 而不是前缀
• 根据这些信息, 我们可以设计出所需的节点类 Node, 它用于存储每个节点的信息
  • Node 类里面需要包含一个{字符->子节点}的字典, 来模拟图中带字符的边
  • 另外 Node 类还要包含一个 boolean, 用于存储当前节点作为终点时是否构成一个完整单词, 初始化为 false
• 接下来我们在 Trie 类中维护一个根节点, 每次操作都从根节点开始
• 在执行 insert 操作时:
  • 维护当前节点, 初始化为根
  • 然后遍历单词的每个字符, 如果当前节点不存在一个对应字符的子节点时, 就创建它
  • 然后将当前节点指向对应的子节点, 继续这个过程直到遍历结束
  • 此时我们将当前节点的 boolean 设置为 true, 表示从根节点到当前节点形成了一个完整的单词
• 对于 search 和 startsWith 操作, 它们唯一的区别就是最终节点是否形成单词, 所以我们可以将共享的逻辑提取出来:
  • 维护当前节点, 初始化为根
  • 然后遍历待查询字符串的每个字符, 如果当前节点不存在一个对应字符的子节点时, 就返回空
  • 否则将当前节点指向对应的子节点, 继续这个过程直到遍历结束
  • 此时的当前节点就是最终节点, 返回它
• 在得到最终节点后:
  • search 操作需要它非空且对应的 boolean 是 true 时才返回 true
  • startsWith 操作只需要它非空就返回 true
• 下面代码中有详细的注释, 方便大家理解

复杂度

• 时间复杂度 O(NC): 假设需要操作 N 次, 每次操作的字符串平均长度为 C, 那么每个操作都需要从根开始最多遍历 C 个节点, 时间复杂度都是 O?, 所以总体时间复杂度就是 O(NC)
• 空间复杂度 O(NC): Trie 中需要存储所有单词的字符, 最差情况下没有重复使用的节点, 空间复杂度就是 O(NC)

代码

class Node:
    def __init__(self):
        # {字符->子节点}字典
        self.children = {}
        # boolean flag判断当前节点结尾时是否构成单词
        self.isWord = False


class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        # 保存根节点
        self.root = Node()

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        # 初始化为根节点
        cur = self.root
        for c in word:
            if c not in cur.children:
                # 子节点不存在时创建它
                cur.children[c] = Node()
            cur = cur.children[c]
        # 根节点->最终节点的路径形成了完整的单词
        cur.isWord = True

    def find(self, word: str) -> Node:
        cur = self.root
        for c in word:
            if c not in cur.children:
                # 子节点不存在时返回空
                return None
            cur = cur.children[c]
        # 返回最终节点
        return cur

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        last_node = self.find(word)
        # 最终节点不为空且形成单词时才返回true
        return last_node is not None and last_node.isWord

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        # 最终节点不为空时返回true
        return self.find(prefix) is not None

---

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊