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

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...