( “树” 之 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 <= 2000word和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的特性所致。所以花了点时间总结实现了更优解决方案,最终实现毫秒级响应。…...
谁在成为产业经济发展的推车人?
区域发展的新蓝图中,京东云能做什么?它的角色是什么?这个问题背后,隐藏的不仅是京东云自身的能力和价值,更是其作为中国互联网云厂商的代表之一,对“技术产业”的新论证。 作者|皮爷 出品|产业家 关于云…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
WPF八大法则:告别模态窗口卡顿
⚙️ 核心问题:阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程,导致后续逻辑无法执行: var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题:…...
【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...
[拓扑优化] 1.概述
常见的拓扑优化方法有:均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有:有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...
数据分析六部曲?
引言 上一章我们说到了数据分析六部曲,何谓六部曲呢? 其实啊,数据分析没那么难,只要掌握了下面这六个步骤,也就是数据分析六部曲,就算你是个啥都不懂的小白,也能慢慢上手做数据分析啦。 第一…...
VSCode 没有添加Windows右键菜单
关键字:VSCode;Windows右键菜单;注册表。 文章目录 前言一、工程环境二、配置流程1.右键文件打开2.右键文件夹打开3.右键空白处打开文件夹 三、测试总结 前言 安装 VSCode 时没有注意,实际使用的时候发现 VSCode 在 Windows 菜单栏…...
LTR-381RGB-01RGB+环境光检测应用场景及客户类型主要有哪些?
RGB环境光检测 功能,在应用场景及客户类型: 1. 可应用的儿童玩具类型 (1) 智能互动玩具 功能:通过检测环境光或物体颜色触发互动(如颜色识别积木、光感音乐盒)。 客户参考: LEGO(乐高&#x…...
AIGC 基础篇 Python基础 02
1.bool类型 书接上回,我们上次最后讲了三大数据类型,除了这三个之外,Python也有bool类型,也就是True和False。 a 2 print(a1) print(a2) 像这里,输出的内容第一个是False,因为a的值为2,而第…...

