208-实现 Trie (前缀树)

antyiwei 发布于2019-08-19 10:50 / 1165人阅读

摘要：前言前缀树是一种很常用的数据结构，例如我们常用的数据库索引。而关于前缀树的介绍，由于中国有关于前缀树的教程，我就不班门弄斧了，我的答案也是参考教程的思路去解答，希望可以给大家一个参考。下面是原题目实现一个前缀树，包含和这三个操作。

前言

前缀树是一种很常用的数据结构，例如我们常用的数据库索引。而关于前缀树的介绍，由于LeetCode中国有关于前缀树的教程，我就不班门弄斧了，我的答案也是参考教程的思路去解答，希望可以给大家一个参考。下面是原题目：

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。示例:
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
说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

解题思路

树是由节点组成，节点定义应该包含节点值(前缀树的定义，值应该为一个字符char)和叶子节点的指针，但是为了识别是否为一个单词的最后一个字符，所以增加一个boolean变量识别。

由于已知输入为全小写(a-z)的字母，所以可以使用一个长度为26的数组存储叶子节点。且由于a-z的ASCII码是连续的，其ASCII是从97-123，所以可以直接使用 ASCII码-97=对应节点的数组下标。

基于数组实现的前缀树

class Trie {
    /**
     * 当前节点的值
     */
    public char value;
    /**
     * a-z有26个字母，需要访问时由于a的ASCII码为97，所以所有字母访问的对应下表皆为 字母的ASCII码-97
     */
    public Trie[] children=new Trie[26];
    /**
     * 标识此节点是否为某个单词的结束节点
     */
    public boolean endAsWord=false;
    
    public Trie() {
        
    }
    /**
     * 插入一个单词
     * @param word 单词
     */
    public void insert(String word) {
        if(word!=null){
            //分解成字符数组
            char[] charArr=word.toCharArray();
            //模拟指针操作,记录当前访问到的树的节点
            Trie currentNode=this;
            for(int i=0;i

云服务器 GPU云服务器 trie树前缀树前缀树 python 前缀表达式c语言实现

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76527.html

javascript 前缀Trie

摘要：很容易看出，前缀最坏情况下的查找也快过二叉搜索树。这种压缩后的被唤作前缀压缩，或直接叫前缀树，字典树。最长公共前缀和的最长公共前缀是，遍历字典树到字母时，此时这些单词的公共前缀是。引子前缀Trie, 又叫字符Tire, trie来自单词retrieval, 一开始念作tree，后来改念try，毕竟它与树是不一样的东西。网上许多文章都搞混了trie与树。 trie是通过边来储存字符...

xiaochao 2019-08-22 14:05 评论0 收藏0
[Leetcode] Implement Trie 实现前缀树

摘要：压缩前缀树其实就是将所有只有一个子节点的节点合并成一个，以减少没有意义的类似链表式的链接。然后我们开始遍历这个前缀树。 Implement Trie Implement a trie with insert, search, and startsWith methods. Note: You may assume that all inputs are consist of lowe...

jsliang 2019-08-14 12:28 评论0 收藏0
以太坊数据结构MPT

摘要：是以太坊存储数据的核心数据结构，它是由和结合的一种树形结构，理解有助于我们更好的理解以太坊的数据存储。所以就有了树压缩前缀树，后面会介绍到，也被称为，中文名称默克尔树，主要用于数据集较大时的文件校验。 MPT(Merkle Patricia Tries)是以太坊存储数据的核心数据结构，它是由Merkle Tree和Patricia Tree结合的一种树形结构，理解MPT有助于我们更...

Honwhy 2019-06-27 18:59 评论0 收藏0
以太坊源码分析--MPT树

摘要：是以太坊中存储区块数据的核心数据结构，它和融合一个树形结构，理解结构对之后学习以太坊区块以及智能合约状态存储结构的模块源码很有帮助。 MPT(Merkle Patricia Tries)是以太坊中存储区块数据的核心数据结构，它Merkle Tree和Patricia Tree融合一个树形结构，理解MPT结构对之后学习以太坊区块header以及智能合约状态存储结构的模块源码很有帮助。首...

roadtogeek 2019-06-27 18:35 评论0 收藏0
Trie树 php 实现敏感词过滤

摘要：在树中，每个节点表示一个状态，每条边表示一个字符，从根节点到叶子节点经过的边即表示一个词条。查找一个词条最多耗费的时间只受词条长度影响，因此的查找性能是很高的，跟哈希算法的性能相当。 Last-Modified: 2019年5月10日15:25:35 参考文章 c++ 使用map实现Trie树关键词过滤扩展，用于检查一段文本中是否出现敏感词，基于Double-Array Trie...

王笑朝 2019-07-01 12:46 评论0 收藏0