当前位置: 首页 > 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;对“技术产业”的新论证。 作者|皮爷 出品|产业家 关于云…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...