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

算法-动态规划/trie树-单词拆分

算法-动态规划/trie树-单词拆分

1 题目概述

1.1 题目出处

https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-interview-150

1.2 题目描述

在这里插入图片描述

2 动态规划

2.1 解题思路

  1. dp[i]表示[0, i)字符串可否构建
  2. 那么dp[i]可构建的条件是,[0,j)可构建且[j,i)包含在wordDict中
  3. 这里你可能会问,那如果是[j,i)不能直接构建,而是有wordDict种的两个单词构建怎么办?其实,因为我们是从低到高构建的动态规划,所以设k > j 且 k <i,那么dp[k] = true,因为dp[j]=true且 [j,k)在wordDict中。那么 [k, i)就是剩下的那个单词了,所以 [j,i)也可以被构建。

2.2 代码

class Solution {public boolean wordBreak(String s, List<String> wordDict) {// dp[i]表示[0, i)字符串可否构建// 那么dp[i]可构建的条件是,[0,j)可构建且[j,i)包含在wordDict中boolean[] dp = new boolean[s.length() + 1];dp[0] = true;Set<String> set = new HashSet<>(wordDict);for (int i = 1; i <= s.length(); i++) {for (int j = 0; j < i; j++) {if (dp[j] == true && set.contains(s.substring(j, i))) {dp[i] = true;break;}}}return dp[s.length()];}
}

2.3 时间复杂度

O(c*s.length)
在这里插入图片描述

2.4 空间复杂度

O( s.length)

3 trie树

3.1 解题思路

  1. 将wordDict构建trie树
  2. 将s从位置0开始往后匹配查找
  3. 如果当前位置能匹配上,继续判断是否是单词结尾,如果是且下一个单词开始的匹配也能成功,就说明能构建,返回true
  4. 其他情况继续往后匹配

3.2 代码

class Solution {Trie root = new Trie();// 记忆数组,用来快速判定该位置是否可以作为单词结尾进行拆分构建boolean[] no = new boolean[300];public boolean wordBreak(String s, List<String> wordDict) {// 将所有word插入字典树for (String word : wordDict)root.insert(word);// 从0个字符开始往后查找,只要匹配成功说明可以构建目标字符串if (root.find(s, 0)) {return true;}return false;}class Trie{public Trie[] children = new Trie[26];// 当前child代表的字符是否是单词结尾boolean isEnd = false;public void insert(String word) {if (null == word || word.length() == 0) {isEnd = true;return;}int index = word.charAt(0) - 'a';Trie child = children[index];if (null == child) {child = new Trie();children[index] = child;}child.insert(word.substring(1));}public boolean find(String s, int i) {// 快速判定当前字符位置是否可以拆分构建// 注意这里必须判定当前节点是否是root,因为我们缓存是从根节点开始的// 否则会对其他child的正常判断过程造成误判if (this == root && no[i]) {return false;}char firstC = s.charAt(i);Trie child = children[firstC - 'a'];if (null == child) {// 如果不能匹配指定位置字符,肯定不可构建if (this == root) {no[i] = true;}return false;}if (child.isEnd) {// 如果能找到目标字符,且字符是单词结尾if (i + 1 == s.length()) {// 如果// 1.已经扫描到字符串最后的字符// 就说明当前位置可以用来拆分构建目标字符串return true;} else {if (root.find(s, i+1)) {// 如果下一个字符往后的字符串能构建// 就说明当前位置可以用来拆分构建目标字符串return true;} else {// 否则说明i+1字符虽是单词结尾,但无法直接拆分构建,记录下来no[i+1] = true;}}}if (i + 1 < s.length()) {// 还未到结尾,可以继续往后查找return child.find(s, i+1);} else {// 已到单词结尾,构建失败return false;}}}
}

3.3 时间复杂度

在这里插入图片描述

3.4 空间复杂度

O(s.length)

参考

  • 循序渐进5种解法,从字典树trie回溯延伸到动态规划

相关文章:

算法-动态规划/trie树-单词拆分

算法-动态规划/trie树-单词拆分 1 题目概述 1.1 题目出处 https://leetcode.cn/problems/word-break/description/?envTypestudy-plan-v2&envIdtop-interview-150 1.2 题目描述 2 动态规划 2.1 解题思路 dp[i]表示[0, i)字符串可否构建那么dp[i]可构建的条件是&…...

React框架核心原理

一、整体架构 三大核心库与对应的组件 history -> react-router -> react-router-dom react-router 可视为react-router-dom 的核心&#xff0c;里面封装了<Router>&#xff0c;<Route>&#xff0c;<Switch>等核心组件,实现了从路由的改变到组件的更新…...

python-pytorch 利用pytorch对堆叠自编码器进行训练和验证

利用pytorch对堆叠自编码器进行训练和验证 一、数据生成二、定义自编码器模型三、训练函数四、训练堆叠自编码器五、将已训练的自编码器级联六、微调整个堆叠自编码器 一、数据生成 随机生成一些数据来模拟训练和验证数据集&#xff1a; import torch# 随机生成数据 n_sample…...

制作 3 档可调灯程序编写

PWM 0~255 可以将数据映射到0 75 150 225 尽可能均匀电压间隔...

源码分享-M3U8数据流ts的AES-128解密并合并---GoLang实现

之前使用C语言实现了一次&#xff0c;见M3U8数据流ts的AES-128解密并合并。 学习了Go语言后&#xff0c;又用Go重新实现了一遍。源码如下&#xff0c;无第三方库依赖。 package mainimport ("crypto/aes""crypto/cipher""encoding/binary"&quo…...

CSDN Q: “这段代码算是在STC89C52RC51单片机上完成PWM呼吸灯了吗?“

这是 CSDN上的一个问题 这段代码算是在STC89C52RC51单片机上完成PWM呼吸灯了吗&#xff0c;还是说得用上定时器和中断函数#include <regx52.h> 我个人认为: 效果上来说, 是的! 码以 以Time / 100-Time 调 Duty, 而 for i loop成 Period, 加上延时, 实现了 PWM周期, 虽然…...

Linux系统编程系列之线程池

Linux系统编程系列&#xff08;16篇管饱&#xff0c;吃货都投降了&#xff01;&#xff09; 1、Linux系统编程系列之进程基础 2、Linux系统编程系列之进程间通信(IPC)-信号 3、Linux系统编程系列之进程间通信(IPC)-管道 4、Linux系统编程系列之进程间通信-IPC对象 5、Linux系统…...

Linux CentOS7 vim多文件与多窗口操作

窗口是可视化的分割区域。Windows中窗口的概念与linux中基本相同。连接xshell就是在Windows中新建一个窗口。而vim打开一个文件默认创建一个窗口。同时&#xff0c;Vim打开一个文件也就会建立一个缓冲区&#xff0c;打开多个文件就会创建多个缓冲区。 本文讨论vim中打开多个文…...

SPI 通信协议

1. SPI通信 1. 什么是SPI通信协议 2. SPI的通信过程 在一开始会先把发送缓冲器的数据&#xff08;8位&#xff09;。一次性放到移位寄存器里。 移位寄存器会一位一位发送出去。但是要先放到锁存器里。然后从机来读取。从机的过程也一样。当移位寄存器的数据全部发送完。其实…...

【图像处理】使用各向异性滤波器和分割图像处理从MRI图像检测脑肿瘤(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

5个适合初学者的初级网络安全工作,网络安全就业必看

前言 网络安全涉及保护计算机系统、网络和数据免受未经授权的访问、破坏和盗窃 - 防止数字活动和数据访问的中断 - 同时也保护用户的资产和隐私。鉴于公共事业、医疗保健、金融以及联邦政府等行业的网络犯罪攻击不断升级&#xff0c;对网络专业人员的需求很高&#xff0c;这并…...

Kafka核心原理

1、Topic的分片和副本机制 分片作用&#xff1a; 解决单台节点容量有限的问题&#xff0c;节点多&#xff0c;效率提升&#xff0c;吞吐量提升。通过分片&#xff0c;将一个大的容器分解为多个小的容器&#xff0c;分布在不同的节点上&#xff0c;从而实现分布式存储。 分片…...

探秘前后端开发世界:猫头虎带你穿梭编程的繁忙街区,解锁全栈之路

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…...

洛谷_分支循环

p2433 问题 5 甲列火车长 260 米&#xff0c;每秒行 12 米&#xff1b;乙列火车长220 米&#xff0c;每秒行 20 米&#xff0c;两车相向而行&#xff0c;从两车车头相遇时开始计时&#xff0c;多长时间后两车车尾相离&#xff1f;已知答案是整数。 计算方式&#xff1a;两车车…...

MySQL数据库入门到精通——进阶篇(3)

黑马程序员 MySQL数据库入门到精通——进阶篇&#xff08;3&#xff09; 1. 锁1.1 锁-介绍1.2 锁-全局锁1.3 锁-表级锁1.3.1 表级锁-表锁1.3.2 表级锁元数据锁( meta data lock&#xff0c;MDL)1.3.3 表级锁-意向锁1.3.4 表级锁意向锁测试 1.4 锁-行级锁1.4.1 行级锁-行锁1.4.2…...

Mind Map:大语言模型中的知识图谱提示激发思维图10.1+10.2

知识图谱提示激发思维图 摘要介绍相关工作方法第一步&#xff1a;证据图挖掘第二步&#xff1a;证据图聚合第三步&#xff1a;LLM Mind Map推理 实验实验设置医学问答长对话问题使用KG的部分知识生成深入分析 总结 摘要 LLM通常在吸收新知识的能力、generation of hallucinati…...

[引擎开发] 杂谈ue4中的Vulkan

接触Vulkan大概也有大半年&#xff0c;概述一下自己这段时间了解到的东西。本文实际上是杂谈性质而非综述性质&#xff0c;带有严重的主观认知&#xff0c;因此并没有那么严谨。 使用Vulkan会带来什么呢&#xff1f;简单来说就是对底层更好的控制。这意味着我们能够有更多的手段…...

docker--redis容器部署及地理空间API的使用示例-II

文章目录 Redis 地理位置类型API命令操作示例JAVA使用示例导入依赖RedisTemplate 操作GeoData示例CityInfo实体类Geo操作接口类Geo操作接口实现类SpringBoot测试类RedissonClient 操作GeoData示例docker–redis容器部署及与SpringBoot整合 docker–redis容器部署及地理空间API的…...

Vue中如何进行文件浏览与文件管理

Vue中的文件浏览与文件管理 文件浏览与文件管理是许多Web应用程序中常见的功能之一。在Vue.js中&#xff0c;您可以轻松地实现文件浏览和管理功能&#xff0c;使您的应用程序更具交互性和可用性。本文将向您展示如何使用Vue.js构建文件浏览器和文件管理功能&#xff0c;以及如…...

jenkins利用插件Active Choices Plug-in达到联动显示或隐藏参数,且参数值可修改

1. 添加组件 Active Choices Plug-in 如jenkins无法联网&#xff0c;可在以下两个地址中下载插件&#xff0c;然后放到/home/jenkins/.jenkins/plugin下面重启jenkins即可 Active Choices Active Choices | Jenkins plugin 2. 效果如下&#xff1a; sharding为空时&#xf…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...