( “树” 之 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
word
和prefix
仅由小写英文字母组成insert
、search
和startsWith
调用次数 总计 不超过 3 ∗ 1 0 4 3 * 10^4 3∗104 次
💡思路:使用数组
我们要定义一个名为TrieNode
的类,它有两个属性:
childs
:这是一个大小为26的数组,表示当前节点的子节点。数组的每个元素代表一个字母(从a
到z
)。如果当前节点有一个子节点(例如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每日一题】
知识点回顾 : Trie,又称前缀树或字典树,用于判断字符串是否存在或者是否具有某种字符串前缀。 ❓208. 实现 Trie (前缀树) 难度:中等 Trie(发音类似 “try”)或者说 前缀树 是一种树形数据结构ÿ…...

算法训练Day40:343. 整数拆分 96.不同的二叉搜索树
文章目录 整数拆分题解(动态规划)贪心 不同的二叉搜索树题解 整数拆分 CategoryDifficultyLikesDislikesContestSlugProblemIndexScorealgorithmsMedium (62.22%)11660--0 Tags 数学 | 动态规划 Companies 给定一个正整数 n ,将其拆分为…...
设计模式及代码
1、工厂方法模式(Factory Method Pattern): 定义一个用于创建对象的接口,让子类决定实例化哪一个类。应用场景:当一个类不知道它所必须创建的对象的类时;一个类希望由它的子类来指定它所创建的对象时。 抽…...

9.java程序员必知必会类库之加密库
前言 密码学在计算机领域源远流长,应用广泛。当前每时每刻,每一个连接到互联网的终端,手机,电脑,iPad都会和互联网有无数次的数据交互,如果这些数据都是明文传输那将是难以想象的。为了保护用户隐私&#…...
C技能树:for循环:九九乘法表
使用for循环,打印九九乘法表。下列四个选项中有一项无法实现该功能,请找出该错误选项。 #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老是蓝屏收集错误信息重启无效怎么办?有用户遇到了电脑开机蓝屏的情况,收集错误信息重启电脑之后,依然无法解决问题。那么这个问题要怎么去进行解决呢?接下来我们来看看以下具体的处理方法教学吧。 准备工作: 1、…...
Redis入门学习笔记【五】Redis在分布式环境下常见的应用场景
一、分布式锁 当多个进程不在同一个系统中,用分布式锁控制多个进程对资源的操作或者访问。 与之对应有线 程锁,进程锁。 分布式锁可以避免不同进程重复相同的工作,减少资源浪费。 同时分布式锁可以避免破坏数据正 确性的发生, …...
Python ZIpFile 解惑:GBK 编码与乱码现象
文章目录 参考描述铺垫乱码现象编码与解码编码解码 字符集Unicode 字符集UTF-8CP437Zip 文件与 CP437 编码 GB2312GB2012GBK 单字节编码与多字节编码 溯源通用标志位与语言编码标志ZipFile 所支持的两种编码方式GBK 编码与 Zip 应用乱码现象产生的原因 解决 参考 项目描述维基…...

【LeetCode】213. 打家劫舍 II
213. 打家劫舍 II(中等) 思路 这道题是 198.打家劫舍 的拓展版,区别在于:本题的房间是环形排列,而198.题中的房间是单排排列。 将房间环形排列,意味着第一间房间和最后一间房间不能同时盗窃,因…...

从初识RabbitMQ到安装了解
一、同步和异步通讯 微服务间通讯有同步和异步两种方式: 同步通讯:就像打电话,需要实时响应。 异步通讯:就像发邮件,不需要马上回复。 两种方式各有优劣,打电话可以立即得到响应,但是你却不…...
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 搭建要求 真实的集群是需要部署在不同的服务器上的,但是在我们测试时同时启动很多个虚拟机内存会吃不消,所以我们通常会搭建伪集群,也就是把所有的服务都搭建在一台虚拟机上,用端口进行区分。 我们这里要…...

【计算机视觉 | 目标检测】OVD:Open-Vocabulary Object Detection 论文工作总结(共八篇)
文章目录 一、2D open-vocabulary object detection的发展和研究现状二、基于大规模外部图像数据集2.1 OVR-CNN:Open-Vocabulary Object Detection Using Captions,CVPR 20212.2 Open Vocabulary Object Detection with Pseudo Bounding-Box Labels&…...

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

( “树” 之 BST) 501. 二叉搜索树中的众数 ——【Leetcode每日一题】
二叉查找树(BST):根节点大于等于左子树所有节点,小于等于右子树所有节点。 二叉查找树中序遍历有序。 ❓501. 二叉搜索树中的众数 难度:简单 给你一个含重复值的二叉搜索树(BST)的根节点 root…...

openharmony内核中不一样的双向链表
不一样的双向链表 链表初识别遍历双向链表参考链接 链表初识别 最近看openharmony的内核源码时看到一个有意思的双向链表,结构如下 typedef struct LOS_DL_LIST{struct LOS_DL_LIST *pstPrev; //前驱节点struct LOS_DL_LIST *pstNext; //后继节点 }LOS_DL_LIST;不…...
大文件删除不在回收站里怎么找回
在日常办公中,总会有一些新的文件产生,和用完后的文件清理掉。有时候不小心误删文件也是常有的事。但如果大文件删除不在回收站里怎么找回呢?遇到的小伙伴们请不要别急,只要按照下面的方法做就行了。 正常情况下删除会进入到回收站中&#x…...

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

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

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

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

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统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? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...

技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?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(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...

MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...