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

208. 实现 Trie (前缀树)

题目描述

Trie(发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。

请你实现 Trie 类:

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word
  • boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false

示例:

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示:

  • 1 <= word.length, prefix.length <= 2000
  • wordprefix 仅由小写英文字母组成
  • insertsearchstartsWith 调用次数 总计 不超过 3 * 104

解答

class Trie {
public:Trie() { // initisEnd = false;memset(next, 0, sizeof(next));}void insert(string word) {// 根节点出发寻找是否有满足word前缀的路径,若有,再添加剩余字母节点即可Trie *node = this;for(char c : word){if(node->next[c - 'a'] == NULL){// 节点中没有该元素,则添加该元素node->next[c - 'a'] = new Trie();}node = node->next[c - 'a'];}node->isEnd = true; // 标记为单词的结尾}bool search(string word) {Trie *node = this;for(char c:word){if(node->next[c - 'a'] == NULL) return false;node = node->next[c - 'a'];}return node->isEnd;}// 检查是否有前缀 prefixbool startsWith(string prefix) {Trie *node = this;for(char c:prefix){if(node->next[c - 'a'] == NULL) return false;node = node->next[c - 'a'];}return true;}private:bool isEnd; // 标识该前缀树节点是否为叶节点Trie *next[26]; // 一个节点最多26个孩子(子树),空间换时间,一个数组(存放26个指针元素)
};/*** Your Trie object will be instantiated and called as such:* Trie* obj = new Trie();* obj->insert(word);* bool param_2 = obj->search(word);* bool param_3 = obj->startsWith(prefix);*/

相关文章:

208. 实现 Trie (前缀树)

题目描述 Trie&#xff08;发音类似 “try”&#xff09;或者说 前缀树 是一种树形数据结构&#xff0c;用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景&#xff0c;例如自动补完和拼写检查。 请你实现 Trie 类&#xff1a; Trie() 初始化前缀树对…...

adb使用总结

adb连接到模拟器 adb devices 打开模拟器&#xff0c;找到设置。 多次点击版本号&#xff0c;切换到开发者模式 搜索进入开发者选项 开启USB调试 此时在终端输入adb devices就连接上了 使用adb查看安卓手机架构 adb shell getprop ro.product.cpu.abi 进入安卓手机的shell …...

go:正确引入自己编写的包(如何在 Go 中正确引入自己编写的包)

前言 目录如下&#xff1a; 具体教程 1. 工作空间&#xff08;我的是根目录&#xff09;新建 go.work 文件 文件内容如下&#xff1a; go 1.21.0use (./tuchuang./tuchuang/testm ) 2. 添加go.mod文件 1. 包文件夹下 进入testm目录执行 go mod init testModule 2. 引用目…...

cortex-A7核PWM实验--STM32MP157

实验目的&#xff1a;驱动风扇&#xff0c;蜂鸣器&#xff0c;马达进行工作 目录 一&#xff0c;PWM相关概念 有源蜂鸣器和无源蜂鸣器 二&#xff0c;分析电路图&#xff0c;框图 三&#xff0c;分析RCC章节 1&#xff0c;确定总线连接 2&#xff0c;根据总线内容确定基…...

电工-学习电工有哪些好处

学习电工有哪些好处&#xff1f;在哪学习电工&#xff1f; 学习电工有哪些好处&#xff1f;在哪学习电工&#xff1f;学习电工可以做什么&#xff1f;优势有哪些&#xff1f; 学习电工可以做什么&#xff1f;学习电工有哪些好处&#xff1f; 就业去向&#xff1a;可在企业单位…...

Redis内存空间预估与内存优化策略:保障数据安全与性能的架构实践AIGC/AI绘画/chatGPT/SD/MJ

推荐阅读 AI文本 OCR识别最佳实践 AI Gamma一键生成PPT工具直达链接 玩转cloud Studio 在线编码神器 玩转 GPU AI绘画、AI讲话、翻译,GPU点亮AI想象空间 资源分享 「java、python面试题」来自UC网盘app分享&#xff0c;打开手机app&#xff0c;额外获得1T空间 https://dr…...

Pandas数据分析教程-数据处理

pandas-02-数据清洗&预处理 B. 数据处理1. 重复值处理2. map逐元素转换3. 值替换4. 改变索引值5. 离散化与分箱6. 检测过滤异常值7. 排列与随机采样8. 根据类别生成one-hot向量,向量化文中用S代指Series,用Df代指DataFrame 数据清洗是处理大型复杂情况数据必不可少的步骤…...

php 多维数组排序,根据某一列排序(array_multisort()和array_column()联用)

array_multisort()和array_column()联用效果直接叠满,11>100 先来看下两个函数的介绍和用法 array_column(): 一般模式,不需要其中字段作为id,只需要提取val值 <?php // 可能从数据库中返回数组 $a [[id > 5698, first_name > Peter, last_name > G…...

框架分析(5)-Django

框架分析&#xff08;5&#xff09;-Django 专栏介绍Django核心概念以及组件讲解模型&#xff08;Model&#xff09;视图&#xff08;View&#xff09;模板&#xff08;Template&#xff09;路由&#xff08;URLconf&#xff09;表单&#xff08;Form&#xff09;后台管理&…...

常见前端面试之VUE面试题汇总七

20. 对 vue 设计原则的理解 1.渐进式 JavaScript 框架&#xff1a;与其它大型框架不同的是&#xff0c;Vue 被设计 为可以自底向上逐层应用。Vue 的核心库只关注视图层&#xff0c;不仅易于上 手&#xff0c;还便于与第三方库或既有项目整合。另一方面&#xff0c;当与现代化的…...

空时自适应处理用于机载雷达——空时处理基础知识(Matla代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

磁盘阵列/视频集中存储/安防监控视频智能分析平台新功能:安全帽/反光衣/安全带AI识别详解

人工智能技术已经越来越多地融入到视频监控领域中&#xff0c;近期我们也发布了基于AI智能视频云存储/安防监控视频AI智能分析平台的众多新功能&#xff0c;该平台内置多种AI算法&#xff0c;可对实时视频中的人脸、人体、物体等进行检测、跟踪与抓拍&#xff0c;支持口罩佩戴检…...

23款奔驰GLE450轿跑升级原厂外观暗夜套件,战斗感满满的

升级的方案基本都是替换原来车身部位的镀铬件&#xff0c;可能会有人问&#xff1a;“难道直接用改色膜贴黑不好吗&#xff1f;”如果是贴膜的话&#xff0c;第一个是颜色没有那么纯正&#xff0c;这些镀铬件贴黑的技术难度先抛开不说&#xff0c;即使贴上去了&#xff0c;那过…...

win10系统rust串口通信实现

一、用cargo创建新工程 命令&#xff1a;cargo new comport use std::env; use std::{thread, time}; use serialport::{DataBits, StopBits, Parity, FlowControl}; use std::io::{self, Read, Write}; use std::time::Duration;fn main() -> io::Result<()> {let m…...

新生代与老年代

在Java虚拟机&#xff08;JVM&#xff09;中&#xff0c;内存被划分为多个不同的区域&#xff0c;其中包括新生代&#xff08;Young Generation&#xff09;和老年代&#xff08;Old Generation&#xff09;。 新生代是用于存储新创建的对象的区域。大多数对象在创建后很快就变…...

Microsoft正在将Python引入Excel

Excel和Python这两个世界正在碰撞&#xff0c;这要归功于Microsoft的新集成&#xff0c;以促进数据分析和可视化 Microsoft正在将流行的编程语言Python引入Excel。该功能的公共预览版现已推出&#xff0c;允许Excel用户操作和分析来自Python的数据。 “您可以使用 Python 绘图…...

知识速递(六)|ChIP-seq分析要点集锦

书接上文组学知识速递&#xff08;五&#xff09;|ChIP-seq知多少&#xff1f;&#xff0c;当我们实验完成&#xff0c;拿到下机数据之后&#xff0c;我们最关心的就是&#xff0c;这个数据能不能用&#xff1f;所谓数据能不能用&#xff0c;其实我们会重点关注以下问题&#x…...

【附安装包】EViews 13.0安装教程|计量经济学|数据处理|建模分析

软件下载 软件&#xff1a;EViews版本&#xff1a;13.0语言&#xff1a;英文大小&#xff1a;369.46M安装环境&#xff1a;Win11/Win10/Win8/Win7硬件要求&#xff1a;CPU2.0GHz 内存4G(或更高&#xff09;下载通道①百度网盘丨64位下载链接&#xff1a;https://pan.baidu.com…...

Java 语言实现快速排序算法

【引言】 快速排序算法是一种常用且高效的排序算法。它通过选择一个基准元素&#xff0c;并将数组分割成两个子数组&#xff0c;一边存放比基准元素小的元素&#xff0c;另一边存放比基准元素大的元素。然后递归地对这两个子数组进行排序&#xff0c;最终达到整个数组有序的目的…...

Config: Git 环境搭建

...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...