当前位置: 首页 > news >正文

【每日一题Day156】LC1032字符流 | 字典树

字符流【LC1032】

设计一个算法:接收一个字符流,并检查这些字符的后缀是否是字符串数组 words 中的一个字符串。

例如,words = ["abc", "xyz"] 且字符流中逐个依次加入 4 个字符 'a''x''y''z' ,你所设计的算法应当可以检测到 "axyz" 的后缀 "xyz"words 中的字符串 "xyz" 匹配。

按下述要求实现 StreamChecker 类:

  • StreamChecker(String[] words) :构造函数,用字符串数组 words 初始化数据结构。
  • boolean query(char letter):从字符流中接收一个新字符,如果字符流中的任一非空后缀能匹配 words 中的某一字符串,返回 true ;否则,返回 false

字典树还是比较熟练了,不熟练的快来练习吧

  • 思路:【字典树】

    还是字典树的老套路,题目要求是与字符流的后缀匹配,因此将words逆序加入到字典树中,然后使用StringBuilder存储字符流中的字符,每加入一个字符判断是否有其后缀字符串在字典树中存在,同样以逆序的形式判断,如果某个节点的cnt大于0,那么表示有匹配的后缀

  • 实现

    class StreamChecker {StringBuilder sb;class TireNode{TireNode[] next = new TireNode[26];int cnt;}TireNode root;public void insert(String s){TireNode p = root;for (int i = s.length() - 1; i >= 0; i--){int u = s.charAt(i) - 'a';if (p.next[u] == null)  p.next[u] = new TireNode();p = p.next[u];}p.cnt++;}public StreamChecker(String[] words) {root = new TireNode();sb = new StringBuilder();for (String word : words){insert(word);}}public boolean query(char letter) {sb.append(letter);TireNode p = root;for (int i = sb.length() - 1; i >= 0; i--){int u = sb.charAt(i) - 'a';if (p.next[u] == null) return false;p = p.next[u];if (p.cnt > 0) return true;}return p.cnt > 0;}
    }/*** Your StreamChecker object will be instantiated and called as such:* StreamChecker obj = new StreamChecker(words);* boolean param_1 = obj.query(letter);*/
    
    • 复杂度
      • 时间复杂度:insert的时间复杂度为O(n)O(n)O(n)nnn为字符串的长度,StreamChecker的时间复杂度为O(mn)O(mn)O(mn)mmm为字符串的大小,query的时间复杂度为O(d)O(d)O(d)ddd为字典树的大小
      • 空间复杂度:O(d)O(d)O(d)

相关文章:

【每日一题Day156】LC1032字符流 | 字典树

字符流【LC1032】 设计一个算法:接收一个字符流,并检查这些字符的后缀是否是字符串数组 words 中的一个字符串。 例如,words ["abc", "xyz"] 且字符流中逐个依次加入 4 个字符 a、x、y 和 z ,你所设计的算法…...

V2G模式下含分布式能源网优化运行研究(Matlab代码实现)

💥💥💞💞欢迎来到本博客❤️❤️💥💥 📋📋📋本文目录如下:🎁🎁🎁 目录 💥1 概述 📚2 运行结果 &am…...

手写一个简单的RPC框架

学习RPC框架,由繁化简,了解其本质原理 文章目录项目简介什么是RPC?项目模块项目代码common模块client模块server模块framework模块测试项目简介 什么是RPC? RPC(Remote Procedure Call)即远程过程调用&am…...

【剑指offer】旋转数组的最小数字

👑专栏内容:剑指offer⛪个人主页:子夜的星的主页💕座右铭:前路未远,步履不停 目录一、题目描述1、题目2、示例示例1示例2二、题目分析1、暴力法2、二分法三、代码汇总1、暴力法2、二分法一、题目描述 1、题…...

【Dorker】Portainer轻量级可视化工具

文章目录Portainer简介登录Portainer第一次登录需创建admin,访问地址:xxx.xxx.xxx.xxx:9000选择local选项卡后本地docker详细信息展示安装nginx私有镜像仓库管理Portainer简介 Portainer是Docker的图形化管理工具,提供状态显示面板、应用模板…...

基于 vue.js 进行组件封装的方案

摘要:本文将介绍如何基于 vue.js 进行组件封装的方案。我们将从分析组件封装的优势开始,然后依次介绍 vue.js 的基本概念,以及如何创建、封装和使用自定义组件。最后,我们将通过一个实际的示例,演示如何实现一个基于 v…...

【Unityc#专题篇】之c#基础篇

👨‍💻个人主页:元宇宙-秩沅 👨‍💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨‍💻 本文由 秩沅 原创 👨‍💻 收录于专栏:uni…...

Python(白银时代)——模块、包、异常

异常 概念 程序运行时,如果Python 解释器遇到了错误,会停止程序运行,并且提示错误信息,这就是异常 程序停止执行并提示错误信息的动作,称为 抛出异常 异常捕获 try: 里面的代码,不确定是否能够正常执行. …...

小程序和Vue写法的区别

小程序和Vue写法的区别主要有以下几点: 语法不同:小程序使用的是WXML、WXSS和JS,而Vue使用的是HTML、CSS和JSX。 数据绑定方式不同:小程序使用的是双向数据绑定,而Vue使用的是单向数据流。 1)在小程序中需…...

如何实现分布式锁

一、锁的作用 锁是为了解决多线程情况下,对于共享资源的访问安全问题。 但是当系统是分布式的时候,本地锁已经没法锁住所需要的资源,因为本地获取了锁,其他系统无法得知本地锁的情况。 分布式锁,是独立于系统的第一方…...

使用VS2019连接Microsoft SQL Server Compact 4.0数据库

简介 SQL Server Compact Edition是微软推出的一个适用于嵌入到移动应用的精简数据库产品,Windows Mobile开发人员能够使用SQL Server CE开发出将数据管理能力延展到Window Mobile移动设备上的应用程序。虽然SQL Server CE占用的磁盘空间只有3到5兆左右&#xff0c…...

Vue2 和 Vue3 的对比

Vue2 vs Vue3 Vue 是一款流行的 JavaScript 框架,用于构建交互式 Web 界面。Vue2 和 Vue3 是 Vue.js 的两个版本。Vue3 是 Vue.js 的最新版本,于 2020 年 9 月正式发布。Vue3 有许多改进和新功能,下面我们将对 Vue2 和 Vue3 进行比较。 性能…...

[数据结构]二叉树的链式存储结构

目录 二叉树的链式存储结构:: 1.创建一颗二叉树 2.二叉搜索树简介 3.前序、中序以及后序遍历 4.层序遍历 5.求一棵树的节点个数代码实现 6.求一棵树的高度代码实现 7.求叶子节点个数代码实现 8.求第K层节点个数代码实现 9.二叉树查找值为x的节点 二叉树…...

黑马程序员 Redis 踩坑及解决

文章目录实战篇p30 短信登录-隐藏用户敏感信息p50 优惠券秒杀-添加优惠券p69 秒杀优化-异步秒杀思路p81 达人探店-点赞排行榜p87 好友关注-实现滚动分页查询问题 1问题 2p90 附近商铺-实现附近商户功能实战篇 p30 短信登录-隐藏用户敏感信息 问题描述:登录后会跳转…...

Matlab实现粒子群算法

粒子群算法(Particle Swarm Optimization,PSO)是一种群体智能算法,通过模拟自然界中鸟群、鱼群等生物群体的行为,来解决优化问题。 在PSO算法中,每个个体被称为粒子,每个粒子的位置表示解空间中…...

tailwindcss 写原生html

需要注意:html文件中引入的是output.css input.css写那三行预留的就可以了打包的时候只要打包html output.css img文件夹句ok,其他都不用原理是运行时生产output.css文件,直接【注意!注意!注意!class"…...

Java开发一年不到,来面试居然敢开口要20K,面完连8K都不想给~

前言 我的好朋友兼大学同学老伍家庭经济情况不错,毕业之后没两年自己存了点钱加上家里的支持,自己在杭州开了一家网络公司。由于公司不是很大所以公司大部分的开发人员都是自己面试的,近期公司发展的不错,打算扩招也面试了不少人…...

LeetCode题解 20(17,79) 电话号码的字母组合,单词搜索<回溯>

文章目录电话号码的字母组合(17)代码解答单词搜索(79)代码解答电话号码的字母组合(17) 思路: 根据题意我们必须根据数字获取对应的字符数组,因此我们先定义1个字符数组表示这个电话表 private String[] letters {"","","abc","…...

路径之谜 蓝桥杯 89

题目描述小明冒充 X 星球的骑士,进入了一个奇怪的城堡。城堡里边什么都没有,只有方形石头铺成的地面。假设城堡地面是 nn 个方格。如下图所示。按习俗,骑士要从西北角走到东南角。可以横向或纵向移动,但不能斜着走,也不…...

Mysql数据库如何调优

MYSQL数据库调优 索引 1、对于常用的查询字段加索引,但如果常用字段只有几个常量值就不需要加索引,或者使用索引会失效的情况; 2、索引失效的情况: ​ 1、索引列使用函数,计算(加减乘除等) …...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

2021-03-15 iview一些问题

1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...