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

【LeetCode】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 仅由小写英文字母组成
  • insertsearch 和 startsWith 调用次数 总计 不超过 3 * 10^4 次

解答

源代码

class Trie {private Trie[] children;private boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;for (int i = 0; i < word.length(); i++) {char ch = word.charAt(i);int index = ch - 'a';if (node.children[index] == null) {node.children[index] = new Trie();}node = node.children[index];}node.isEnd = true;}public boolean search(String word) {return searchPrefix(word) != null && searchPrefix(word).isEnd;}public boolean startsWith(String prefix) {return searchPrefix(prefix) != null;}private Trie searchPrefix(String prefix) {Trie node = this;for (int i = 0; i < prefix.length(); i++) {char ch = prefix.charAt(i);int index = ch - 'a';if (node.children[index] == null) {return null;}node = node.children[index];}return node;}
}/*** 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);*/

总结

有些复杂啊……第一次没折腾出来放弃了,第二次才AC了。

官解用的其实相当于一个26叉数,成员变量children数组表示的是下一个字母,0索引对应' a ',25索引对应' z ';isEnd表示当前字母是否为一个单词的末尾。

相关文章:

【LeetCode】208.实现Trie(前缀树)

题目 Trie&#xff08;发音类似 "try"&#xff09;或者说 前缀树 是一种树形数据结构&#xff0c;用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景&#xff0c;例如自动补完和拼写检查。 请你实现 Trie 类&#xff1a; Trie() 初始化前缀…...

多线程笔记: volatile、synchronized、Monitor等

为什么非volatile变量也有线程可见性&#xff1f;不加volatile也可以看到变量变化是为什么&#xff1f;Thread.sleep() 和 System.out.println() 与内存可见性的影响Thread.sleep() 对线程可见性的影响&#xff1f;Java中的Monitor监视器是什么&#xff1f; Slf4j public clas…...

shell语法--数组相关

shell定义一个数组 在 shell 中&#xff0c;可以使用以下语法来定义一个数组&#xff1a; array_name(item1 item2 item3 ...) 其中&#xff0c;array_name 是数组的名称&#xff0c;item1、item2、item3 等是数组中的元素&#xff0c;它们之间用空格分隔。例如&#xff0c;以下…...

AI:05 - 基于深度学习的道路交通信号灯的检测与识别

随着人工智能的快速发展,基于深度学习的视觉算法在道路交通领域中起到了重要作用。本文将探讨如何利用深度学习技术实现道路交通信号灯的检测与识别,通过多处代码实例展示技术深度。 道路交通信号灯是指示交通参与者行驶和停止的重要信号。准确地检测和识别交通信号灯对于智…...

The Sandbox 即将参加韩国区块链周,并带来一系列独家周边活动!

韩国区块链周&#xff08;Korea Blockchain Week&#xff09;即将到来&#xff0c;届时将有成千上万的 NFT 项目、建设者、社区成员、企业家、投资者和爱好者齐聚首尔&#xff0c;分享 Web3 的最新更新和未来愿景。 继成功举办韩流崛起 LAND 销售并宣布多个合作伙伴关系之后&a…...

Mysql高阶语句 (一)

一、常用查询 &#xff08;增、删、改、查&#xff09; 对 MySQL 数据库的查询&#xff0c;除了基本的查询外&#xff0c;有时候需要对查询的结果集进行处理。 例如只取 10 条数据、对查询结果进行排序或分组等等 1、按关键字排序 PS:类比于windows 任务管理器 使用 SELECT 语句…...

win10 ping不通 Docker ip(解决截图)

背景&#xff1a; win10下载了docker desktop就是这个图&#xff0c;然后计划做一个springboot连接docker。 docker部署springboot :docker 部署springboot(成功、截图)_總鑽風的博客-CSDN博客 问题&#xff1a;spring boot部署docker后&#xff0c;docker接口通了&#xff0…...

讲讲几道关于 TCP/UDP 通信的面试题

TCP &#xff08;1&#xff09;TCP 的 accept 发生在三次握手的哪个阶段&#xff1f; 如下图connect和accept的关系&#xff1a; accept过程发生在三次握手之后&#xff0c;三次握手完成后&#xff0c;客户端和服务器就建立了tcp连接并可以进行数据交互了。这时可以调用accep…...

golang 连接 oracle 数据库 增删改查

1&#xff0c;golang 连接 oracle 数据库 2&#xff0c;增删改查 /** Author: lmy* Date: 2023-08-24 15:19:22* LastEditors: lmy* LastEditTime: 2023-08-24 16:23:58* FilePath: \golangOracleDemo\main.go* Description: golang oracle 增删改查 DEMO*/package mainimpor…...

Unity——音频管理器(附例子)

在实际游戏开发中&#xff0c;音效既是一个相对独立的部分&#xff0c;又与其他游戏逻辑密切关联。也就是说&#xff0c;与音效相关的代码会插入很多细节代码中。 而且在音效非常丰富的情况下&#xff0c;如果每一个游戏模块都单独播放音效&#xff0c;那么可能会带来一些问题…...

TCP协议基础

一&#xff1a; TCP协议是什么&#xff1f; TCP协议是基于面向连接&#xff0c;可靠传输&#xff0c;基于字节流的传输层通信协议 1. 面向连接 TCP协议是一种面向连接的协议&#xff0c;意味着在双方在建立数据传输之前&#xff0c;需要进行一个逻辑上的连接&#xff0c;且是…...

C# NetTopologySuite+ProjNet 任意图形类型坐标转换

添加引用&#xff1a;NetTopologySuite、ProjNet、ProjNet.SRID Program.cs文件&#xff1a; using ProjNet.CoordinateSystems; using ProjNet.CoordinateSystems.Transformations; using ProjNet.SRID; using System; using System.Collections.Generic; using System.Linq;…...

Windows笔记本电脑开机黑屏

Windows笔记本电脑开机黑屏 最近&#xff0c;我遇到了一件奇怪的事情。我的Windows笔记本电脑在开机时出现了一个黑屏&#xff0c;没有任何反应。我尝试了多种方法&#xff0c;包括重启和恢复出厂设置&#xff0c;但都无济于事。 我开始感到担心&#xff0c;因为这只会影响到…...

Samb共享用户的设置和修改Linux用户的id号,修改Linux组的id号,加入组,删除组成员等

零、samba帐号的设置 为samba共享添加用户&#xff0c;并设定仅能由授权用户进入的共享 #增加没有家目录&#xff0c;也无法登录系统的空用户 useradd -M userA -s /sbin/nologin #-M 选项是--no-create-home的简写形式&#xff0c;即不为该用户配置家目录&#xff1b;-s选项&…...

VBA:对Excel单元格进行合并操作

Sub hb()Dim nn 3For i 3 To 18If Range("b" & i) <> Range("b" & i 1) ThenRange("b" & n & ":b" & i).Mergen i 1End IfNextEnd Sub...

HTML5离线储存

简介 离线存储指的是&#xff1a;在用户没有与因特网连接时&#xff0c;可以正常访问站点或应用&#xff0c;在用户与因特网连接时&#xff0c;更新用户机器上的缓存文件。 原理&#xff1a;HTML5的离线存储是基于一个新建的 .appcache 文件的缓存机制(不是存储技术)&#xf…...

cmd: Union[List[str], str], ^ SyntaxError: invalid syntax

跑项目在调用from easyprocess import EasyProcess 遇到报错&#xff1a; cmd: Union[List[str], str], ^ SyntaxError: invalid syntax猜测是EasyProcess版本与python版本不对应 pip show EasyProcess查证一下&#xff1a; WARNING: pip is being invoked by an old…...

2023高教社杯数学建模思路 - 案例:异常检测

文章目录 赛题思路一、简介 -- 关于异常检测异常检测监督学习 二、异常检测算法2. 箱线图分析3. 基于距离/密度4. 基于划分思想 建模资料 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 一、简介 – 关于异常…...

FFDNet-pytorch版本代码测试教程

一、FFDNet-pytorch版本代码下载 &#xff08;1&#xff09;FFDNet-pytorch下载 https://download.csdn.net/download/qq_41104871/88233742 二、FFDNet-pytorch版本代码运行环境配置 &#xff08;1&#xff09;FFDNet-pytorch版本代码运行环境配置 https://blog.csdn.net/q…...

uni-app项目由hbuilder项目转化为cli项目

1.背景 原uni-app项目是通过hbuilder创建的&#xff0c;运行以及打包都要依赖于hbuilder运行&#xff1b;一般在vscode开发&#xff0c;在hbuilder运行比较怪异&#xff1b;后续希望脱离hbuilder运行并能通过构建平台进行打包&#xff0c;因此将hbuilder项目转化为cli项目 2.…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...