实现 Trie (前缀树)

难度: Medium

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 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数总计不超过 3 * 10⁴ 次

Submission

运行时间: 78 ms

内存: 27.8 MB

class Trie:

    def __init__(self):
        self.trie = {}

    def insert(self, word: str) -> None:
        tmp = self.trie
        for ch in word:
            if ch not in tmp:
                tmp[ch] = {}
            tmp = tmp[ch]
        tmp['#'] = '#'

    def search(self, word: str) -> bool:
        tmp = self.trie
        for ch in word:
            if ch not in tmp:
                return False
            tmp = tmp[ch]
        return '#' in tmp

    def startsWith(self, prefix: str) -> bool:
        tmp = self.trie
        for ch in prefix:
            if ch not in tmp:
                return False
            tmp = tmp[ch]
        return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Explain

这个题解使用 Trie（字典树）数据结构来实现字符串的快速插入、查询和前缀匹配。Trie 中的每个节点表示一个字符，从根节点到某一节点的路径表示该节点对应的字符串。在插入字符串时，从根节点出发，沿着字符串的字符遍历 Trie，如果对应的子节点不存在，则创建一个新的子节点。查询时，同样沿着字符串的字符遍历 Trie，如果某个字符对应的子节点不存在，则说明 Trie 中不包含该字符串。如果遍历到最后一个字符的节点，且该节点是一个词的末尾（可用一个特殊字符 '#' 表示），则说明 Trie 中存在该字符串。前缀匹配时，只需判断能否在 Trie 中找到前缀对应的路径即可。

时间复杂度: O(m)，其中 m 为字符串的长度

空间复杂度: O(n * k)，其中 n 为字符串的平均长度，k 为字符串的数量

class Trie:

    def __init__(self):
        # 初始化根节点，用字典表示 Trie
        self.trie = {}

    def insert(self, word: str) -> None:
        # 从根节点开始遍历
        tmp = self.trie
        for ch in word:
            # 如果当前字符不在当前节点的子节点中，则创建一个新的子节点
            if ch not in tmp:
                tmp[ch] = {}
            # 继续遍历下一个子节点
            tmp = tmp[ch]
        # 在单词的末尾节点处加入一个特殊字符，表示单词的结束
        tmp['#'] = '#'

    def search(self, word: str) -> bool:
        # 从根节点开始遍历
        tmp = self.trie
        for ch in word:
            # 如果当前字符不在当前节点的子节点中，则说明单词不存在
            if ch not in tmp:
                return False
            # 继续遍历下一个子节点
            tmp = tmp[ch]
        # 判断单词是否是完整的单词（以特殊字符结尾）
        return '#' in tmp

    def startsWith(self, prefix: str) -> bool:
        # 从根节点开始遍历
        tmp = self.trie
        for ch in prefix:
            # 如果当前字符不在当前节点的子节点中，则说明前缀不存在
            if ch not in tmp:
                return False
            # 继续遍历下一个子节点
            tmp = tmp[ch]
        # 如果能遍历完前缀的所有字符，则说明前缀存在
        return True

Explore

使用字典存储 Trie 节点的优点包括灵活性和空间效率。字典允许动态地添加和查找字符，不需要预先定义数组的大小，适用于字符种类多样的情况。此外，字典只存储实际存在的字符，可以节省空间。然而，字典的缺点是相较于数组，其查找和插入操作可能较慢，因为字典的内部实现复杂度高于简单的数组索引。使用固定大小数组的优点是访问速度快，因为可以直接通过字符的 ASCII 值计算索引，操作时间复杂度为 O(1)。缺点是可能会浪费空间，特别是当字符集很大时，许多数组元素可能为空，尤其是在存储稀疏数据时。

使用特殊字符`#`来标识单词的结束和使用布尔标志`isEnd`的主要区别在于实现方式。使用`#`字符的方法需要在字典中添加一个特殊的键，其值通常为自身或者一个标记值，这种方法使得结束标记与其他字符的存储方式一致，便于统一处理。而使用布尔标志`isEnd`则需要在每个节点中额外存储一个布尔值，此方法直观且容易理解。从性能角度看，布尔标志`isEnd`可能更优，因为它不需要为结束标志单独存储额外的键值对，节省了空间。此外，布尔值的检查通常比字典键的检查要快。

除了使用`#`字符标记之外，其他方法可包括：1. 使用已提及的布尔标志`isEnd`，在每个节点中设置一个布尔值来直接标识该节点是否代表一个单词的结束。这种方法可以直接判断最后一个字符的节点的`isEnd`值，如果为真，则表示字符串完整存储在 Trie 中。2. 在节点中维护一个计数器或列表，记录该节点作为单词结尾的次数或具体单词，这适用于需要统计单词出现次数或记录多个单词共用节点的场景。这些方法各有优劣，实际使用中可根据具体需求和性能考量选择适合的方法。