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

实现 Trie (前缀树)

题目链接

实现 Trie (前缀树)

题目描述

注意点

  • word 和 prefix 仅由小写英文字母组成

解答思路

  • 首先要理解前缀树是什么,参照该篇文章【图解算法】模板+变式——带你彻底搞懂字典树(Trie树)
  • 在了解前缀树是什么后,设计前缀树就会更加容易,因为本题中所有单词都仅由小写英文字母组成,所以哈希表只需要26个空间即可,若有些单词具有相同的前缀,则可视为它们有相同的父节点,也就是相当于构造一棵最大有26个子节点的二叉树,构造树的过程可以由以下图片表示:

代码

class Trie {TrieNode root;public Trie() {root = new TrieNode();}public void insert(String word) {TrieNode currNode = root;for (char c : word.toCharArray()) {if (currNode.childNode[c - 'a'] == null) {currNode.childNode[c - 'a'] = new TrieNode();}currNode = currNode.childNode[c - 'a'];}currNode.isWord = true;}public boolean search(String word) {TrieNode currNode = root;for (char c : word.toCharArray()) {if (currNode.childNode[c - 'a'] == null) {return false;}currNode = currNode.childNode[c - 'a'];}if (!currNode.isWord) {return false;}return true;}public boolean startsWith(String prefix) {TrieNode currNode = root;for (char c : prefix.toCharArray()) {if (currNode.childNode[c - 'a'] == null) {return false;}currNode = currNode.childNode[c - 'a'];}return true;}
}class TrieNode {boolean isWord;TrieNode[] childNode = new TrieNode[26];
}

关键点

  • 学习前缀树的相关知识
  • 构造前缀树的过程

相关文章:

实现 Trie (前缀树)

题目链接 实现 Trie (前缀树) 题目描述 注意点 word 和 prefix 仅由小写英文字母组成 解答思路 首先要理解前缀树是什么,参照该篇文章【图解算法】模板变式——带你彻底搞懂字典树(Trie树)在了解前缀树是什么后,设计前缀树就会更加容易,…...

ElasticSearch基础知识汇总

文章目录 前言一、认识ElasticSearch1.正向索引和倒排索引2. MySql与ElasticSearc3.IK分词器 二、ES索引库操作1.mapping映射属性2.索引库的CRUD 三、ES文档库操作 前言 Elasticsearch是一个基于Lucene的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基…...

服务器数据库中了locked勒索病毒怎么办,locked勒索病毒恢复工具

最近一段时间网络上的locked勒索病毒非常嚣张,自从6月份以来,很多企业的计算机服务器数据库遭到了locked勒索病毒的攻击,起初locked勒索病毒攻击用友畅捷通T用户,后来七月份开始攻击金蝶云星空客户,导致企业的财务系统…...

没有 JavaScript 计时器的自动播放轮播 - CSS 动画

先看效果&#xff1a; 再看代码&#xff08;查看更多&#xff09;&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>计时器</title><style>* {padding: 0;margin: 0;box-siz…...

《Flink学习笔记》——第三章 Flink的部署模式

不同的应用场景&#xff0c;有时候对集群资源的分配和占用有不同的需求。所以Flink为各种场景提供了不同的部署模式。 3.1 部署模式&#xff08;作业角度/通用分类&#xff09; 根据集群的生命周期、资源的分配方式、main方法到底在哪里执行——客户端还是Client还是JobManage…...

网络安全(黑客技术)0基础学习手册

目录梗概 一、自学网络安全学习的误区和陷阱 二、学习网络安全的一些前期准备 三、网络安全学习路线 四、学习资料的推荐 想自学网络安全&#xff08;黑客技术&#xff09;首先你得了解什么是网络安全&#xff01;什么是黑客&#xff01; 网络安全可以基于攻击和防御视角来…...

腾讯云服务器价格表大全_轻量服务器_CVM云服务器报价明细

腾讯云服务器租用费用表&#xff1a;轻量应用服务器2核2G4M带宽112元一年&#xff0c;540元三年、2核4G5M带宽218元一年&#xff0c;2核4G5M带宽756元三年、云服务器CVM S5实例2核2G配置280.8元一年、GPU服务器GN10Xp实例145元7天&#xff0c;腾讯云服务器网长期更新腾讯云轻量…...

vue中bus的使用和涉及到的问题

创建一个js文件 import Vue from "Vue" export default new Vue 我们可以直接在要使用的页面中引用使用 import bus from /assets/js/eventBus.js;bus.$emit("info", "123") // 使用bus.$on("info", (val) > { // 接收console.l…...

Flink的简要概述

以下是Flink的各种架构的简要概述&#xff1a; 1. Flink概述&#xff1a;Apache Flink是一个开源的流处理和批处理框架&#xff0c;具有高性能、容错性和数据一致性保证。它支持事件驱动的流处理和批量处理&#xff0c;并提供了丰富的API和工具来处理实时数据流和大规模数据集…...

多线程下的signal信号处理

多线程中&#xff0c;信号在哪个线程中处理是不确定的&#xff0c;可能被任意一个线程处理 下边的代码可以验证该结论&#xff0c;多次Ctrlc&#xff0c;会被不同的线程捕获此信号&#xff0c;并处理&#xff0c;最终每个线程死锁&#xff0c;阻塞在等待锁的状态 #include &l…...

〖Python网络爬虫实战㉞〗- 图形验证码OCR识别

订阅&#xff1a;新手可以订阅我的其他专栏。免费阶段订阅量1000 python项目实战 Python编程基础教程系列&#xff08;零基础小白搬砖逆袭) 说明&#xff1a;本专栏持续更新中&#xff0c;订阅本专栏前必读关于专栏〖Python网络爬虫实战〗转为付费专栏的订阅说明作者&#xff1…...

Python Scrapy网络爬虫框架从入门到实战

Python Scrapy是一个强大的网络爬虫框架&#xff0c;它提供了丰富的功能和灵活的扩展性&#xff0c;使得爬取网页数据变得简单高效。本文将介绍Scrapy框架的基本概念、用法和实际案例&#xff0c;帮助你快速上手和应用Scrapy进行数据抓取。 Scrapy是一个基于Python的开源网络爬…...

后端面试话术集锦第四篇:ElasticSearch面试话术

🚗后端面试集锦目录 💖后端面试话术集锦第 1 篇:spring面试话术💖 💖后端面试话术集锦第 2 篇:spring boot面试话术💖 💖后端面试话术集锦第 3 篇:spring cloud面试话术💖 💖后端面试话术集锦第 4 篇:ElasticSearch面试话术💖 💖后端面试话术集锦第 5 …...

C++之ifstream成员函数get、tellg、eof实例(一百八十五)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 人生格言&#xff1a; 人生…...

安卓webview,网页端生成安卓项目(极速生成)教程

安卓webview&#xff0c;网页端生成安卓项目&#xff08;极速生成&#xff09;教程 一&#xff0c;前言 当自己做了一个PC端的页面&#xff0c;也就是前端的页面&#xff0c;或者已经上服的页面&#xff0c;但也想生成一个安卓端供用户使用&#xff0c;本教程详细讲解如何把前…...

如何在vscode导入下载的插件安装包

点击vscode插件 --> 点击3个点 --> 选择从VSIX安装 点击更新报 Cannot update while running on a read-only volume. The application is on a read-only volume. Please move the application and try again. If you’re on macOS Sierra or later, you’ll need to m…...

springboot 多线程实战

先说下业务场景&#xff0c;业务1&#xff1a;基于实时轨迹数据打卡&#xff0c;业务2&#xff1a;基于非实时轨迹的时间差&#xff0c;计算累计时长。 简单点说就是从websocket获取到的实时数据&#xff0c;既要兼容不耗时操作&#xff0c;又要兼容耗时操作。 单线程做的话&a…...

求生之路2社区服务器sourcemod安装配置搭建教程centos

求生之路2社区服务器sourcemod安装配置搭建教程centos 大家好我是艾西&#xff0c;通过上文我们已经成功搭建了求生之路2的服务端。但是这个服务端是纯净的服务端&#xff0c;就是那种最纯粹的原版。如果想要实现插件、sm开头的命令等功能&#xff0c;需要安装这个sourcemod。…...

通达OAV12版本,表单及流程,定制开发总结

通达OA-V12版本&#xff0c;表单及流程&#xff0c;定制开发总结 触发器金蝶系统对接 日期&#xff1a;2023年8月29日 触发器 一键转交操作&#xff0c;不会调用触发器。 解决办法&#xff1a;可以按需要按步骤&#xff0c;关闭一键转交按钮。这里会隐藏一键转交、一键结束按钮…...

浅析Linux 物理内存外碎片化

本文出现的内核代码来自Linux4.19&#xff0c;如果有兴趣&#xff0c;读者可以配合代码阅读本文。 一、Linux物理内存外碎片化概述 什么是Linux物理内存碎片化&#xff1f;Linux物理内存碎片化包括两种&#xff1a; 1.物理内存内碎片&#xff1a;指分配给用户的内存空间中未…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...