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

( “树” 之 Trie) 208. 实现 Trie (前缀树) ——【Leetcode每日一题】

知识点回顾Trie,又称前缀树字典树,用于判断字符串是否存在或者是否具有某种字符串前缀。
在这里插入图片描述

❓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 ∗ 1 0 4 3 * 10^4 3104

💡思路:使用数组

我们要定义一个名为TrieNode的类,它有两个属性:

  • childs:这是一个大小为26的数组,表示当前节点的子节点。数组的每个元素代表一个字母(从az)。如果当前节点有一个子节点(例如a),则childs数组的相应位置(即索引0)将包含一个TrieNode对象。
  • isLeaf:这是一个布尔值,表示当前节点是否为叶子节点。如果当前节点是叶子节点,则此值为true;否则为false

🍁代码:(Java、C++)

Java

class Trie {private class TrieNode{TrieNode[] childs = new TrieNode[26];boolean isLeaf;}private TrieNode root = new TrieNode();public Trie() {}public void insert(String word) {insert(word, root);}private void insert(String word, TrieNode root){if(root == null) return;if(word.length() == 0){root.isLeaf = true;return;}int index = indexForChar(word.charAt(0));if(root.childs[index] == null){root.childs[index] = new TrieNode();}insert(word.substring(1), root.childs[index]);}private int indexForChar(char c){return c - 'a';}public boolean search(String word) {return search(word, root);}private boolean search(String word, TrieNode root){if(root == null) return false;if(word.length() == 0) return root.isLeaf;int index = indexForChar(word.charAt(0));return search(word.substring(1), root.childs[index]);}public boolean startsWith(String prefix) {return startsWith(prefix, root);}private boolean startsWith(String prefix, TrieNode root){if(root == null) return false;if(prefix.length() == 0) return true;int index = indexForChar(prefix.charAt(0));return startsWith(prefix.substring(1), root.childs[index]);}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/

C++

class Trie {
private:vector<Trie*> childs;bool isLeaf;Trie* searchPrefix(string prefix) {Trie* node = this;for (char ch : prefix) {ch -= 'a';if (node->childs[ch] == nullptr) {return nullptr;}node = node->childs[ch];}return node;}public:Trie() : childs(26), isLeaf(false) {}void insert(string word) {Trie* node = this;for (char ch : word) {ch -= 'a';if (node->childs[ch] == nullptr) {node->childs[ch] = new Trie();}node = node->childs[ch];}node->isLeaf= true;}bool search(string word) {Trie* node = this->searchPrefix(word);return node != nullptr && node->isLeaf;}bool startsWith(string prefix) {return this->searchPrefix(prefix) != nullptr;}
};/*** 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);*/

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度:初始化为 O ( 1 ) O(1) O(1),其余操作为 O ( ∣ S ∣ ) O(|S|) O(S),其中 ∣ S ∣ ∣S∣ S 是每次插入或查询的字符串的长度。
  • 空间复杂度 O ( ∣ T ∣ ⋅ Σ ) O(|T|\cdot\Sigma) O(TΣ),其中 ∣ T ∣ |T| T 为所有插入字符串的长度之和, Σ \Sigma Σ 为字符集的大小,本题 Σ = 26 \Sigma=26 Σ=26

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!

相关文章:

( “树” 之 Trie) 208. 实现 Trie (前缀树) ——【Leetcode每日一题】

知识点回顾 &#xff1a; Trie&#xff0c;又称前缀树或字典树&#xff0c;用于判断字符串是否存在或者是否具有某种字符串前缀。 ❓208. 实现 Trie (前缀树) 难度&#xff1a;中等 Trie&#xff08;发音类似 “try”&#xff09;或者说 前缀树 是一种树形数据结构&#xff…...

算法训练Day40:343. 整数拆分 96.不同的二叉搜索树

文章目录 整数拆分题解&#xff08;动态规划&#xff09;贪心 不同的二叉搜索树题解 整数拆分 CategoryDifficultyLikesDislikesContestSlugProblemIndexScorealgorithmsMedium (62.22%)11660--0 Tags 数学 | 动态规划 Companies 给定一个正整数 n &#xff0c;将其拆分为…...

设计模式及代码

1、工厂方法模式&#xff08;Factory Method Pattern&#xff09;&#xff1a; 定义一个用于创建对象的接口&#xff0c;让子类决定实例化哪一个类。应用场景&#xff1a;当一个类不知道它所必须创建的对象的类时&#xff1b;一个类希望由它的子类来指定它所创建的对象时。 抽…...

9.java程序员必知必会类库之加密库

前言 密码学在计算机领域源远流长&#xff0c;应用广泛。当前每时每刻&#xff0c;每一个连接到互联网的终端&#xff0c;手机&#xff0c;电脑&#xff0c;iPad都会和互联网有无数次的数据交互&#xff0c;如果这些数据都是明文传输那将是难以想象的。为了保护用户隐私&#…...

C技能树:for循环:九九乘法表

使用for循环&#xff0c;打印九九乘法表。下列四个选项中有一项无法实现该功能&#xff0c;请找出该错误选项。 #include <stdio.h> int main(int argc, char** argv) {int i 0;int j 0;(_____1_____)return 0; } int row 0; int col 0; for(i 0; i < 8…...

Win10老是蓝屏收集错误信息重启无效怎么办?

Win10老是蓝屏收集错误信息重启无效怎么办&#xff1f;有用户遇到了电脑开机蓝屏的情况&#xff0c;收集错误信息重启电脑之后&#xff0c;依然无法解决问题。那么这个问题要怎么去进行解决呢&#xff1f;接下来我们来看看以下具体的处理方法教学吧。 准备工作&#xff1a; 1、…...

Redis入门学习笔记【五】Redis在分布式环境下常见的应用场景

一、分布式锁 当多个进程不在同一个系统中&#xff0c;用分布式锁控制多个进程对资源的操作或者访问。 与之对应有线 程锁&#xff0c;进程锁。 分布式锁可以避免不同进程重复相同的工作&#xff0c;减少资源浪费。 同时分布式锁可以避免破坏数据正 确性的发生&#xff0c; …...

Python ZIpFile 解惑:GBK 编码与乱码现象

文章目录 参考描述铺垫乱码现象编码与解码编码解码 字符集Unicode 字符集UTF-8CP437Zip 文件与 CP437 编码 GB2312GB2012GBK 单字节编码与多字节编码 溯源通用标志位与语言编码标志ZipFile 所支持的两种编码方式GBK 编码与 Zip 应用乱码现象产生的原因 解决 参考 项目描述维基…...

【LeetCode】213. 打家劫舍 II

213. 打家劫舍 II&#xff08;中等&#xff09; 思路 这道题是 198.打家劫舍 的拓展版&#xff0c;区别在于&#xff1a;本题的房间是环形排列&#xff0c;而198.题中的房间是单排排列。 将房间环形排列&#xff0c;意味着第一间房间和最后一间房间不能同时盗窃&#xff0c;因…...

从初识RabbitMQ到安装了解

一、同步和异步通讯 微服务间通讯有同步和异步两种方式&#xff1a; 同步通讯&#xff1a;就像打电话&#xff0c;需要实时响应。 异步通讯&#xff1a;就像发邮件&#xff0c;不需要马上回复。 两种方式各有优劣&#xff0c;打电话可以立即得到响应&#xff0c;但是你却不…...

MySQL(六)-字符串函数的使用解析

字符串函数的使用解析 1 计算字符串字符数的函数和字符串长的函数2 合并字符串函数 CONCAT(s1,s2,...)、CONCAT_WS(xs1,s2,...)3 替换字符串函数INSERT(s1,x,len,s2)4 字母大小写转换函数5 获取指定长度的字符串的函数LEFT(s,n)和RIGHT(s,n)6 填充字符串的函数 LPAD(s1,len,s2)…...

Zookeeper集群搭建

搭建Zookeeper集群 1.1 搭建要求 真实的集群是需要部署在不同的服务器上的&#xff0c;但是在我们测试时同时启动很多个虚拟机内存会吃不消&#xff0c;所以我们通常会搭建伪集群&#xff0c;也就是把所有的服务都搭建在一台虚拟机上&#xff0c;用端口进行区分。 我们这里要…...

【计算机视觉 | 目标检测】OVD:Open-Vocabulary Object Detection 论文工作总结(共八篇)

文章目录 一、2D open-vocabulary object detection的发展和研究现状二、基于大规模外部图像数据集2.1 OVR-CNN&#xff1a;Open-Vocabulary Object Detection Using Captions&#xff0c;CVPR 20212.2 Open Vocabulary Object Detection with Pseudo Bounding-Box Labels&…...

C++入门基础知识[博客园长期更新......]

0.博客园链接 博客的最新内容都在博客园当中&#xff0c;所有内容均为原创(博客园、CSDN同步更新)。 C知识点集合 1.命名空间 在往后的C编程中&#xff0c;将会存在大量的变量和函数&#xff0c;因为有大量的变量和函数&#xff0c;所以C的库会非常多。那么在C语言编程中&a…...

( “树” 之 BST) 501. 二叉搜索树中的众数 ——【Leetcode每日一题】

二叉查找树&#xff08;BST&#xff09;&#xff1a;根节点大于等于左子树所有节点&#xff0c;小于等于右子树所有节点。 二叉查找树中序遍历有序。 ❓501. 二叉搜索树中的众数 难度&#xff1a;简单 给你一个含重复值的二叉搜索树&#xff08;BST&#xff09;的根节点 root…...

openharmony内核中不一样的双向链表

不一样的双向链表 链表初识别遍历双向链表参考链接 链表初识别 最近看openharmony的内核源码时看到一个有意思的双向链表&#xff0c;结构如下 typedef struct LOS_DL_LIST{struct LOS_DL_LIST *pstPrev; //前驱节点struct LOS_DL_LIST *pstNext; //后继节点 }LOS_DL_LIST;不…...

大文件删除不在回收站里怎么找回

在日常办公中&#xff0c;总会有一些新的文件产生&#xff0c;和用完后的文件清理掉。有时候不小心误删文件也是常有的事。但如果大文件删除不在回收站里怎么找回呢?遇到的小伙伴们请不要别急&#xff0c;只要按照下面的方法做就行了。 正常情况下删除会进入到回收站中&#x…...

Ubuntu22.04部署Pytorch2.0深度学习环境

文章目录 安装Anaconda创建新环境安装Pytorch2.0安装VS CodeUbuntu下实时查看GPU状态的方法小实验&#xff1a;Ubuntu、Windows10下GPU训练速度对比 Ubuntu安装完显卡驱动、CUDA和cudnn后&#xff0c;下面部署深度学习环境。 &#xff08;安装Ubuntu系统、显卡驱动、CUDA和cudn…...

php的面试集结(会持续更新)

PHP 高级工程面试题汇总 php面试 1.大型的分页查询 发现当表中有很多上万条数据时&#xff0c;越后的数据用limit分页显示就越慢&#xff08;>2秒&#xff09;&#xff0c;可能是mysql的特性所致。所以花了点时间总结实现了更优解决方案&#xff0c;最终实现毫秒级响应。…...

谁在成为产业经济发展的推车人?

区域发展的新蓝图中&#xff0c;京东云能做什么&#xff1f;它的角色是什么&#xff1f;这个问题背后&#xff0c;隐藏的不仅是京东云自身的能力和价值&#xff0c;更是其作为中国互联网云厂商的代表之一&#xff0c;对“技术产业”的新论证。 作者|皮爷 出品|产业家 关于云…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...