当前位置: 首页 > 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 环境搭建

...

XCTF-web-easyupload

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

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

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

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

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...