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

OJ练习第182题——字典树(前缀树)

字典树(前缀树)

  • 208. 实现 Trie (前缀树)
    • 题目描述
    • 示例
    • 知识补充
    • 官解代码
  • 211. 添加与搜索单词 - 数据结构设计
    • 题目描述
    • 示例
    • 思路
    • Java代码

208. 实现 Trie (前缀树)

力扣链接:208. 实现 Trie (前缀树)

题目描述

在这里插入图片描述

示例

在这里插入图片描述

知识补充

在这里插入图片描述
插入字符串

我们从字典树的根开始,插入字符串。对于当前字符对应的子节点,有两种情况:

子节点存在。沿着指针移动到子节点,继续处理下一个字符。
子节点不存在。创建一个新的子节点,记录在 children 数组的对应位置上,然后沿着指针移动到子节点,继续搜索下一个字符。

重复以上步骤,直到处理字符串的最后一个字符,然后将当前节点标记为字符串的结尾。

查找前缀

我们从字典树的根开始,查找前缀。对于当前字符对应的子节点,有两种情况:

子节点存在。沿着指针移动到子节点,继续搜索下一个字符。
子节点不存在。说明字典树中不包含该前缀,返回空指针。
重复以上步骤,直到返回空指针或搜索完前缀的最后一个字符。

若搜索到了前缀的末尾,就说明字典树中存在该前缀。此外,若前缀末尾对应节点的 isEnd 为真,则说明字典树中存在该字符串。

官解代码

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) {Trie node = searchPrefix(word);return node != null && node.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;}
}作者:力扣官方题解
链接:https://leetcode.cn/problems/implement-trie-prefix-tree/solutions/717239/shi-xian-trie-qian-zhui-shu-by-leetcode-ti500/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

211. 添加与搜索单词 - 数据结构设计

力扣链接:211. 添加与搜索单词 - 数据结构设计

题目描述

在这里插入图片描述

示例

在这里插入图片描述

思路

根据题意,WordDictionary 类需要支持添加单词和搜索单词的操作,可以使用字典树实现。

对于添加单词,将单词添加到字典树中即可。

对于搜索单词,从字典树的根结点开始搜索。由于待搜索的单词可能包含点号,因此在搜索过程中需要考虑点号的处理。对于当前字符是字母和点号的情况,分别按照如下方式处理:

如果当前字符是字母,则判断当前字符对应的子结点是否存在,如果子结点存在则移动到子结点,继续搜索下一个字符,如果子结点不存在则说明单词不存在,返回 false;

如果当前字符是点号,由于点号可以表示任何字母,因此需要对当前结点的所有非空子结点继续搜索下一个字符。

重复上述步骤,直到返回 false 或搜索完给定单词的最后一个字符。

如果搜索完给定的单词的最后一个字符,则当搜索到的最后一个结点的 isEnd 为 true 时,给定的单词存在。

特别地,当搜索到点号时,只要存在一个非空子结点可以搜索到给定的单词,即返回 true。

Java代码

class WordDictionary {private Trie root;public WordDictionary() {root = new Trie();}public void addWord(String word) {root.insert(word);}public boolean search(String word) {return dfs(word, 0, root);}private boolean dfs(String word, int index, Trie node) {if(index == word.length()) {return node.isEnd();}char ch = word.charAt(index);if(Character.isLetter(ch)) {int childIndex = ch - 'a';Trie child = node.getChildren()[childIndex];if(child != null && dfs(word, index + 1, child)) {return true;}}else {for(int i = 0; i < 26; i++) {Trie child = node.getChildren()[i];if(child != null && dfs(word, index + 1, child)) {return true;}}}return false;}
}
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 Trie[] getChildren() {return children;}public boolean isEnd() {return isEnd;}
}

相关文章:

OJ练习第182题——字典树(前缀树)

字典树&#xff08;前缀树&#xff09; 208. 实现 Trie (前缀树)题目描述示例知识补充官解代码 211. 添加与搜索单词 - 数据结构设计题目描述示例思路Java代码 208. 实现 Trie (前缀树) 力扣链接&#xff1a;208. 实现 Trie (前缀树) 题目描述 示例 知识补充 插入字符串 我…...

前端知识总结

在前端开发中&#xff0c;y x是一种常见的自增运算符的使用方式。它表示将变量x的值自增1&#xff0c;并将自增后的值赋给变量y。 具体来说&#xff0c;x是一种后缀自增运算符&#xff0c;表示将变量x的值自增1。而y x则是将自增前的值赋给变量y。这意味着在执行y x之后&am…...

中国JP-10燃料行业市场研究与预测报告(2023版)

内容简介&#xff1a; 高密度燃料是指以石油基、煤基和生物质基烃类为原料&#xff0c;通过聚合、加氢、异构等工艺合成的密度大于0.85 gcm-3的饱和多环碳氢化合物&#xff0c;广泛应用于航空航天领域。由于高密度燃料密度大和体积热值高等特点&#xff0c;飞行器在油箱体积一…...

护眼灯显色指数应达多少?眼科医生推荐灯光显色指数多少合适

台灯的显色指数是其非常重要的指标&#xff0c;它可以表示灯光照射到物体身上&#xff0c;物体颜色的真实程度&#xff0c;一般用平均显色指数Ra来表示&#xff0c;Ra值越高&#xff0c;灯光显色能力越强。常见的台灯显色指数最低要求一般是在Ra80以上即可&#xff0c;比较好的…...

AI 大模型

随着人工智能技术的迅猛发展&#xff0c;AI 大模型逐渐成为推动人工智能领域提升的关键因素&#xff0c;大模型已成为了引领技术浪潮研究和应用方向。大模型即大规模预训练模型&#xff0c;通常是指那些在大规模数据上进行了预训练的具有庞大规模和复杂结构的人工智能模型&…...

一个案例熟悉使用pytorch

文章目录 1. 完整模型的训练套路1.2 导入必要的包1.3 准备数据集1.3.1 使用公开数据集&#xff1a;1.3.2 获取训练集、测试集长度&#xff1a;1.3.3 利用 DataLoader来加载数据集 1.4 搭建神经网络1.4.1 测试搭建的模型1.4.2 创建用于训练的模型 1.5 定义损失函数和优化器1.6 使…...

MySQL - limit 分页查询 (查询操作 五)

功能介绍&#xff1a;分页查询&#xff08;limit&#xff09;是一种常用的数据库查询技术&#xff0c;它允许我们从数据库表中按照指定的数量和顺序获取数据&#xff0c;它在处理大量数据时特别有用&#xff0c;可以提高查询效率并减少网络传输的数据 语法&#xff1a;SELECT …...

代码随想录笔记--动态规划篇

1--动态规划理论基础 动态规划经典问题&#xff1a;① 背包问题&#xff1b;② 打家劫舍&#xff1b;③ 股票问题&#xff1b; ④ 子序列问题&#xff1b; 动态规划五部曲&#xff1a; ① 确定 dp 数组及其下标的含义&#xff1b; ② 确定递推公式&#xff1b; ③ 确定 dp 数组…...

vue之vuex

Vuex 是 Vue.js 的一个状态管理模式和库&#xff0c;为应用中的所有组件提供了一个集中式的存储管理&#xff0c;并提供了一种强大的方式来管理应用的状态。Vuex 包含以下核心概念&#xff1a; State&#xff1a;定义了应用的状态&#xff0c;类似于组件中的 data。 Getters&a…...

ISO 26262 系列学习笔记 ———— ASIL定义(Automotive Safety Integration Level)

文章目录 介绍严重度&#xff08;Severity&#xff09;暴露概率&#xff08;Probability of Exposure&#xff09;可控性&#xff08;Controllability&#xff09; 介绍 如果没有另行说明&#xff0c;则应满足ASIL A、B、C和D各分条款的要求或建议。这些要求和建议参考了安全目…...

代码随想录 第8章 二叉树

1、理论知识 &#xff08;1&#xff09;、满二叉树 如果一棵二叉树只有度为0的节点和度为2的节点&#xff0c;并且度为0的节点在同一层上&#xff0c;则这棵二叉树为满二叉树。 &#xff08;2&#xff09;、完全二叉树 除了底层节点可能没有填满&#xff0c;其余每层的节点…...

计算机网络工程师多选题系列——计算机网络

2 计算机网络 2.1 网络技术基础 题型1 TCP/IP与ISO模型的问题 TCP/IP由IETF制定&#xff0c;ISO由OSI制定&#xff1b; TCP/IP分为四层&#xff0c;分别是主机-网络层、互联网络层、传输层和应用层&#xff1b;OSI分为七层&#xff0c;分别是物理层、数据链路层、网络层(实…...

Zabbix5.0_介绍_组成架构_以及和prometheus的对比_大数据环境下的监控_网络_软件_设备监控_Zabbix工作笔记001

z 这里Zabbix可以实现采集 存储 展示 报警 但是 zabbix自带的,展示 和报警 没那么好看,我们可以用 grafana进行展示,然后我们用一个叫睿象云的来做告警展示, 会更丰富一点. 可以看到 看一下zabbix的介绍. 对zabbix的介绍,这个zabbix比较适合对服务器进行监控 这个是zabbix的…...

Spring | 事件监听器应用与最佳实践

引言 在复杂的软件开发环境中&#xff0c;组件之间的通信和信息交流显得尤为重要。Spring框架&#xff0c;作为Java世界中最受欢迎的开发框架之一&#xff0c;提供了一种强大的事件监听器模型&#xff0c;使得组件间的通信变得更加灵活和解耦。本文主要探讨Spring事件监听器的…...

正点原子lwIP学习笔记——NETCONN接口简介

1. NETCONN接口简介 NETCONN API 使用了操作系统的 IPC 机制&#xff0c; 对网络连接进行了抽象&#xff0c;使用同一的接口完成UDP和TCP连接。 NETCONN API接口是在RAW接口基础上延申出来的一套API接口 首先会调用netconn_new创建一个pcb控制块&#xff0c;其实际是一个宏定…...

PHP自动识别采集何意网址文章正文内容

在做PHP采集内容时&#xff0c;用过querylist采集组件&#xff0c;但是这个插件采集页面内容时&#xff0c;都必须要写个采集选择器。这样比较麻烦&#xff0c;每个文章页面都必须指定一条采集规则 。就开始着手找一个插件可以能自动识别任意文章url正文内容并采集的&#xff0…...

区块链实验室(27) - 区块链+物联网应用案例

分享最新的区块链物联网应用案例&#xff1a;HPCLS-BC...

NPU上PyTorch模型训练问题案例

在昇腾AI处理器上训练PyTorch框架模型时&#xff0c;可能由于环境变量设置问题、训练脚本代码问题&#xff0c;导致打印出的堆栈报错与实际错误并不一致、脚本运行异常等问题&#xff0c;那么本期就分享几个关于PyTorch模型训练问题的典型案例&#xff0c;并给出原因分析及解决…...

出现 conda虚拟环境默认放在C盘 解决方法

目录 1. 问题所示2. 原理分析3. 解决方法3.1 方法一3.2 方法二1. 问题所示 通过conda配置虚拟环境的时候,由于安装在D盘下,但是配置的环境默认都给我放C盘 通过如下命令:conda env list,最后查看该环境的确在C盘下 2. 原理分析 究其根本原因,这是因为默认路径没有足够的…...

Ubuntu Postgresql开机自启动服务

1. 建立service文件 sudo vim /etc/systemd/system/postgresql.service2. postgresql service文件 [Unit] DescriptionPostgreSQL 14 database server Documentationman:postgres(1) Documentationhttp://www.postgresql.org/docs/14/static/ Afternetwork.target[Service] T…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...