首页 > 其他分享 >Trie-前缀查询

Trie-前缀查询

时间:2023-10-12 22:11:54浏览次数:40  
标签:Node 前缀 Trie class next 查询 public isWord cur

Tire专门为处理字符串设计的。

  • 平衡二叉树,查询复杂度是O(logn)
  • 但是100万个条目,2^20,logn大约20.
  • 但是Tire的复杂度,和字段中一共有多少条目无关!世间复杂度为O(w),w为查询单词的长度
  • 大多数的单词长度小于10

图示

整个字符串以字母为单位拆开

cat、dog、deer、panda

 

可以看出

每个节点有26个指向下一节点的指针。(不考虑大小写)(不同的内容,子树数量不确定。)

从根节点出发,有26个子树。

class Node{

  char c;

  Map<char, Node> next;

}

 

继而,在找cat的时候,寻找c之前,就已经知道目标地址存储c了。

所以这样表达就可以。

class Node{

  Map<char, Node> next;

}

 

叶子结点 单词的结尾靠叶子结点不能表示出。

panda中 pan是平底锅的结尾 , 所以要加一个布尔值,判断每个节点是否是一个单词。

class Node{

  boolean isWord;

  Map<char, Node> next;

}

代码实现

import java.util.TreeMap;

/**
 * trie数定义
 */
public class Trie {
    /*
     * 子节点
     */
    private class Node{
        public boolean isWord;
        //默认节点是字符型,不采用泛型来设计。字符串是由一个字符组成的。主要用于字符串。主要用于英语语境
        public TreeMap<Character, Node> next;

        public Node(boolean isWord){
            this.isWord = isWord;
            next = new TreeMap<>();
        }
        public Node(){
            this(false);
        }
    }

    private Node root;
    private int size;

    public Trie(){
        root = new Node();
        size = 0;
    }

    public int getSize(){
        return size;
    }

    /**
     * 新增单词的方法
     * @param word
     */
    public void add(String word){
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if(cur.next.get(c) == null){
                cur.next.put(c, new Node());
            }
            cur = cur.next.get(c);
        }
        if(!cur.isWord){
            cur.isWord = true;
            size++;
        }
    }

}

 

标签:Node,前缀,Trie,class,next,查询,public,isWord,cur
From: https://www.cnblogs.com/jiangym/p/17760720.html

相关文章

  • 加密的手机号,如何模糊查询?
    前言前几天,知识星球中有位小伙伴,问了我一个问题:加密的手机号如何模糊查询?我们都知道,在做系统设计时,考虑到系统的安全性,需要对用户的一些个人隐私信息,比如:登录密码、身份证号、银行卡号、手机号等,做加密处理,防止用户的个人信息被泄露。很早之前,CSDN遭遇了SQL注入,导致了600多万......
  • java项目使用Mybatis-Plus插件,QueryWrapper日期开始-结束范围查询
    1、参数开始日期startTime、结束日期endTime挺好用,开始日期、结束日期当天都包含进去了,如果使用qw.between("create_time",startTime,endTime)方法是不含endTime结束日期当天的qw.apply(bCulresCardMvVO.getStartTime()!=null,"date_format(create_time,......
  • 面试官:MySQL数据查询太多会OOM吗
    我的主机内存只有100G,现在要全表扫描一个200G大表,会不会把DB主机的内存用光?逻辑备份时,可不就是做整库扫描吗?若这样就会把内存吃光,逻辑备份不是早就挂了?所以大表全表扫描,看起来应该没问题。这是为啥呢?1、全表扫描对server层的影响假设,我们现在要对一个200G的InnoDB表db1.t,执行一个......
  • [扫盲]在linux上查询gpu占用
    参考资料:how-to-measure-gpu-usage按显卡厂家来区分:NvidiaGPU:nvidia-smi或者gpustatIntelGPU:intel-gpu-toolsAmdGPU:aticonfig--odgc--odgt......
  • Python word'str'(字符串前缀string prefix)的种类
    Python字符串前缀(Stringprefix) r'string'r'',用法是不会对后方字符串中的转义符进行转义,如: str=r'\n'print(str)#会直接输出\n,并不会输出换行 f'string'f'',用法是对字符进行格式化就和str.format()一样,会对{}进行格式化,如: str=f'你好,{}'......
  • Docker内时区查询和修改方法
    利用【dockerexec-it容器ID/bin/bash】命令进入Docker容器内,执行【date】命令查看Docker容器的时间发现与宿主机有误差时,修改时间和时区。方法一:在【宿主机】中执行命令,【dockercp/etc/localtime容器ID:/etc/localtime】,重启Docker容器。方法二:在【宿主机】中执行命......
  • 实现查询学霸积分榜(当前赛季)
             ......
  • Python搭建数据查询接口服务
    启动一个服务,使用FastAPI框架,增加跨域允许1#-*-coding:UTF-8-*-2"""3@author:cc4@file:service.py5@time:2021/05/246"""78importsqlite39fromfastapiimportFastAPI10importuvicorn11importos12fromfastapi.......
  • Python selenium chrome版本查询和对应驱动下载
    elenium爬虫需要安装Chrome驱动chrome版本查询和对应驱动下载,超详细方法/步骤1查看谷歌的版本,第一步在地址栏输入图中网址第二步查看版本号2复制版本号,只需复制版本号最后一位小数点之前的数字。(例:版本号:111.0.5563.65,复制111.0.5563即可)将复制的版本号......
  • 定位SQL慢查询
    一、概念MySQL的慢查询(慢查询日志):是MySQL提供的一种日志记录,用来记录在MySQL中响应时间超过阈值的语句。具体环境中,运行时间超过long_query_time值的SQL语句,则会被记录到慢查询日志中。long_query_time的默认值为10,意思是记录运行10秒以上的语句。默认情况下,MySQL数据库并不启......