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 <= 2000word和prefix仅由小写英文字母组成insert、search和startsWith调用次数 总计 不超过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(发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。 请你实现 Trie 类: Trie() 初始化前缀树对…...
adb使用总结
adb连接到模拟器 adb devices 打开模拟器,找到设置。 多次点击版本号,切换到开发者模式 搜索进入开发者选项 开启USB调试 此时在终端输入adb devices就连接上了 使用adb查看安卓手机架构 adb shell getprop ro.product.cpu.abi 进入安卓手机的shell …...
go:正确引入自己编写的包(如何在 Go 中正确引入自己编写的包)
前言 目录如下: 具体教程 1. 工作空间(我的是根目录)新建 go.work 文件 文件内容如下: go 1.21.0use (./tuchuang./tuchuang/testm ) 2. 添加go.mod文件 1. 包文件夹下 进入testm目录执行 go mod init testModule 2. 引用目…...
cortex-A7核PWM实验--STM32MP157
实验目的:驱动风扇,蜂鸣器,马达进行工作 目录 一,PWM相关概念 有源蜂鸣器和无源蜂鸣器 二,分析电路图,框图 三,分析RCC章节 1,确定总线连接 2,根据总线内容确定基…...
电工-学习电工有哪些好处
学习电工有哪些好处?在哪学习电工? 学习电工有哪些好处?在哪学习电工?学习电工可以做什么?优势有哪些? 学习电工可以做什么?学习电工有哪些好处? 就业去向:可在企业单位…...
Redis内存空间预估与内存优化策略:保障数据安全与性能的架构实践AIGC/AI绘画/chatGPT/SD/MJ
推荐阅读 AI文本 OCR识别最佳实践 AI Gamma一键生成PPT工具直达链接 玩转cloud Studio 在线编码神器 玩转 GPU AI绘画、AI讲话、翻译,GPU点亮AI想象空间 资源分享 「java、python面试题」来自UC网盘app分享,打开手机app,额外获得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
框架分析(5)-Django 专栏介绍Django核心概念以及组件讲解模型(Model)视图(View)模板(Template)路由(URLconf)表单(Form)后台管理&…...
常见前端面试之VUE面试题汇总七
20. 对 vue 设计原则的理解 1.渐进式 JavaScript 框架:与其它大型框架不同的是,Vue 被设计 为可以自底向上逐层应用。Vue 的核心库只关注视图层,不仅易于上 手,还便于与第三方库或既有项目整合。另一方面,当与现代化的…...
空时自适应处理用于机载雷达——空时处理基础知识(Matla代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
磁盘阵列/视频集中存储/安防监控视频智能分析平台新功能:安全帽/反光衣/安全带AI识别详解
人工智能技术已经越来越多地融入到视频监控领域中,近期我们也发布了基于AI智能视频云存储/安防监控视频AI智能分析平台的众多新功能,该平台内置多种AI算法,可对实时视频中的人脸、人体、物体等进行检测、跟踪与抓拍,支持口罩佩戴检…...
23款奔驰GLE450轿跑升级原厂外观暗夜套件,战斗感满满的
升级的方案基本都是替换原来车身部位的镀铬件,可能会有人问:“难道直接用改色膜贴黑不好吗?”如果是贴膜的话,第一个是颜色没有那么纯正,这些镀铬件贴黑的技术难度先抛开不说,即使贴上去了,那过…...
win10系统rust串口通信实现
一、用cargo创建新工程 命令: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虚拟机(JVM)中,内存被划分为多个不同的区域,其中包括新生代(Young Generation)和老年代(Old Generation)。 新生代是用于存储新创建的对象的区域。大多数对象在创建后很快就变…...
Microsoft正在将Python引入Excel
Excel和Python这两个世界正在碰撞,这要归功于Microsoft的新集成,以促进数据分析和可视化 Microsoft正在将流行的编程语言Python引入Excel。该功能的公共预览版现已推出,允许Excel用户操作和分析来自Python的数据。 “您可以使用 Python 绘图…...
知识速递(六)|ChIP-seq分析要点集锦
书接上文组学知识速递(五)|ChIP-seq知多少?,当我们实验完成,拿到下机数据之后,我们最关心的就是,这个数据能不能用?所谓数据能不能用,其实我们会重点关注以下问题&#x…...
【附安装包】EViews 13.0安装教程|计量经济学|数据处理|建模分析
软件下载 软件:EViews版本:13.0语言:英文大小:369.46M安装环境:Win11/Win10/Win8/Win7硬件要求:CPU2.0GHz 内存4G(或更高)下载通道①百度网盘丨64位下载链接:https://pan.baidu.com…...
Java 语言实现快速排序算法
【引言】 快速排序算法是一种常用且高效的排序算法。它通过选择一个基准元素,并将数组分割成两个子数组,一边存放比基准元素小的元素,另一边存放比基准元素大的元素。然后递归地对这两个子数组进行排序,最终达到整个数组有序的目的…...
Config: Git 环境搭建
...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
