当前位置: 首页 > 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;指分配给用户的内存空间中未…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...