前缀树（Trie）

题解思路

1. Trie 树的基本结构

Trie 树（前缀树） 是一种 多叉树，适用于快速 字符串查找 和 前缀匹配。它的基本特点：

• 每个 节点 代表一个 字符。
• 从根节点到某个节点的路径 表示一个字符串的前缀。
• 标记终止符 来区分完整单词。

Leetcode 54.实现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$。

输入描述

• 第一行输入一个整数 n，表示操作的次数。
• 接下来 n 行，每行包含一个操作：
  • "insert word"：插入 word。
  • "search word"：查询 word 是否存在，输出 true 或 false。
  • "startsWith prefix"：查询是否存在以 prefix 为前缀的字符串，输出 true 或 false。

输出描述

对于 search 和 startsWith 操作，输出 true 或 false，其余操作不输出

样例1

输入

6
insert apple
search apple
search app
startsWith app
insert app
search app

输出

true
false
true
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$次