力扣208-实现前缀树

208. 实现 Trie (前缀树) - 力扣LeetCodeTrie发音类似 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); // 返回 Truetrie.search(app); // 返回 Falsetrie.startsWith(app); // 返回 Truetrie.insert(app);trie.search(app); // 返回 True提示1 word.length, prefix.length 2000word和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 为 root2.如果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 为 root2.如果word[i]不是 cur 的儿子返回 0search 和 startsWith 收到 0 之后返回 false3.更新 cur 为儿子列表中的相应节点4.遍历结束如果 cur 的 end 是 false返回 1否则返回 25.search 如果收到的是 2返回 true否则返回 false6.startsWith 如果收到的是非 0 数字返回 true否则返回 falseclass 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