力扣208-实现前缀树

208. 实现 Trie (前缀树) - 力扣（LeetCode）

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 * 104次

如果单词只有 a 和 b 两个字母，那么就变成了一个二叉树。假设 a 是左子节点，b 是右子节点（即 a 往左走，b 往右走）

insert : 假设插入 aabb，那么相当于新增一条“左、左、右、右”的二叉树路径，标记最后一个节点为终止节点。如果再插入 aabba，那么相当于一条“左、左、右、右、左”的二叉树路径，给刚刚的路径的终止节点新增一个左子节点，并标记这个左子节点为终止节点即可

search : 例如查找字符串 aabb，相当于在二叉树中查找是否存在一个“左、左、右、右”的路径且最后一个节点为终止节点

starswith : 相当于 search，只不过不需要“最后一个节点为终止节点”这么苛刻

现在是单词，也就是26个字母的排列组合，那么就从二叉树变成二十六叉树。26叉树的每个节点包含一个长为26的儿子节点列表，还有一个布尔变量 end 标记该节点是否为终止节点。

insert :

1.遍历 word，用 cur 表示当前字符在树的哪个节点，初始时 cur 为 root

2.如果word[i]不是 cur 的儿子，就创建一个节点 node 作为 cur 的儿子。如果word[i]为 a，那么 cur 的 son 数组中的son[0]就等于这个新创建的节点 node，后面的字符以此类推

3.更新 cur 为儿子列表中的相应节点

4.word 遍历完毕，将 cur 的 end 设置为 true

因为 startwith 和 search 的过程高度重叠，因此可以通用一个 find 函数：

1.遍历字符串 word，用变量 cur 表示当前字符在树的哪个节点，初始时 cur 为 root

2.如果word[i]不是 cur 的儿子，返回 0，search 和 startsWith 收到 0 之后返回 false

3.更新 cur 为儿子列表中的相应节点

4.遍历结束，如果 cur 的 end 是 false，返回 1，否则返回 2

5.search 如果收到的是 2，返回 true，否则返回 false

6.startsWith 如果收到的是非 0 数字，返回 true，否则返回 false

class Trie: def __init__(self) : self.root = Node() def insert(self, word: str) -> None : cur = self.root # 表示当前遍历到的字符在树中的位置 for c in word : if c not in cur.son : cur.son[c] = Node() cur = cur.son[c] cur.end = True # 遍历完成，标记终止节点 def find(self, word : str) -> int : cur = self.root for c in word : if c not in cur.son : return 0 cur = cur.son[c] return 2 if cur.end else 1 # 如果遍历到最后发现最后一个字符刚好是终止节点，说明完全匹配，search 返回 true def search(self, word: str) -> bool : return self.find(word) == 2 def startsWith(self, prefix: str) -> bool : return self.find(prefix) != 0 class Node : __slots__ = 'son', 'end' def __init__(self) : self.son = {} self.end = False