leetcode hot100单词拆分

在本题中,我们是要把一个字符串,判断是否能用给的字符串数组中的单词进行拆分,如果可以则返回true,不能的话则返回false。这个题一开始看无法与背包问题联系在一起。但仔细考虑,就是用物品(给的字符串数组中的单词)去装背包(给定的字符串)。如果可以凑成,那么就返回true。
并且题目中所说的单词可以重复使用,也就是完全背包问题。并且我们要考虑,这个题是否需要考虑遍历顺序拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 举例。
“apple”, “pen” 是物品,那么我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。
“apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的,那么我们就是强调物品之间顺序。
所以我们要先遍历背包再遍历物品。并且可以重复使用,
dp[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词
如果确定dp[j] 是true,且 [j, i] 这个区间的子串出现在字典里,那么dp[i]一定是true。(j < i )。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
从递推公式中可以看出,dp[i] 的状态依靠 dp[j]是否为true,那么dp[0]就是递推的根基,dp[0]一定要为true,否则递推下去后面都都是false了。
那么dp[0]有没有意义呢?
dp[0]表示如果字符串为空的话,说明出现在字典里。
但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况,那么dp[0]初始为true完全就是为了推导公式。
下标非0的dp[i]初始化为false,只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词
class Solution {public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> set = new HashSet<>(wordDict);boolean[] valid = new boolean[s.length() + 1];valid[0] = true;for (int i = 1; i <= s.length(); i++) {for (int j = 0; j < i; j++) {if (set.contains(s.substring(j, i)) && valid[j]) {valid[i] = true;}}}return valid[s.length()];}
}
注意,本题中创建了一个新的 HashSet 实例,并使用 wordDict 集合的元素进行初始化。这意味着 set 中的所有元素都将是 wordDict 中的元素,但不包含任何重复项,因为 HashSet 是一个不允许重复元素的集合。
s.substring(j,i)表示截取字符串s下标从j到i的字串,这里是左闭右开的区间。所以j只能小于i,如果等于i的话,下面截取的时候就会出错。
相关文章:
leetcode hot100单词拆分
在本题中,我们是要把一个字符串,判断是否能用给的字符串数组中的单词进行拆分,如果可以则返回true,不能的话则返回false。这个题一开始看无法与背包问题联系在一起。但仔细考虑,就是用物品(给的字符串数组中…...
大数据构建知识图谱:从技术到实战的完整指南
文章目录 大数据构建知识图谱:从技术到实战的完整指南一、概述二、知识图谱的基础理论定义与分类核心组成历史与发展 三、知识获取与预处理数据源选择数据清洗实体识别 四、知识表示方法知识表示模型RDFOWL属性图模型 本体构建关系提取与表示 五、知识图谱构建技术图…...
WebServer -- 定时器处理非活动连接(上)
目录 🍍函数指针 🌼基础知识 🐙整体概述 🎂基础API sigaction 结构体 sigaction() sigfillset() SIGALRM, SIGTERM 信号 alarm() socketpair() send() 📕信号通知流程 统一事件源 信号处理机制 &#x…...
微服务部署:金丝雀发布、蓝绿发布和滚动发布的对比
金丝雀发布、蓝绿发布和滚动发布的对比 金丝雀发布、蓝绿发布和滚动发布都是软件发布策略,它们都旨在降低发布风险并提高发布速度。但是,这三种策略在工作方式、优缺点等方面存在一些差异。 工作方式 金丝雀发布:将新版本软件逐步发布给用…...
轻松入门MySQL:优化复杂查询,使用临时表简化数据库查询流程(13)
在进销存管理系统中,复杂的数据查询是司空见惯的。这些查询往往需要处理大量的数据,并执行复杂的逻辑操作。然而,处理这些查询可能会变得非常耗时,并且难以维护。为了解决这个问题,我们可以利用临时表,这是…...
vmware的ubuntu虚拟机因空间满无法启动
正在虚拟机编译android源代码,没注意空间不足,结果回来发现了 Assuming drive cache: write through 的问题,经查是空间不足的原因 按照这个教程,清除出来部分空间,才能进去系统,并且对系统空间做下优化 …...
Unity数据持久化之PlayerPrefs
这里写目录标题 PlayerPrefs概述基本方法PlayerPrefs存储位置实践小项目反射知识补充数据管理类的创建反射存储数据----常用成员反射存储数据----List成员反射存储数据----Dictionary成员反射存储数据----自定义类成员反射读取数据----常用成员反射读取数据----List成员反射读取…...
uniapp微信公众号H5分享
如果项目文件node_modules中没有weixin-js-sdk文件,则直接使用本文章提供的; 如果不生效,则在template.h5.html中引入 <script src"https://res.wx.qq.com/open/js/jweixin-1.6.0.js"></script> 首先引入weixin-js-…...
深入理解指针(c语言)
目录 一、使用指针访问数组二、数组名的理解1、数组首元素的地址2、整个数组 三、一维数组传参的本质四、冒泡排序五、二级指针六、指针数组 一、使用指针访问数组 可以使用指针来访问数组元素。例如,可以声明一个指针变量并将其指向数组的第一个元素,然…...
高级语言期末2015级唐班B卷
1.编写函数,按照如下公式计算圆周率π的值(精确到1e-5) #include <stdio.h>double pai() {double last0;double flag1;int n1;while(flag-last>1e-5) {lastflag;flag*1.0*(2*n)*(2*n)/((2*n-1)*(2*n1));n;}return 2*last; }int main…...
开发一款招聘小程序需要具备哪些功能?
随着时代的发展,找工作的方式也在不断变得简单,去劳务市场、人才市场的方式早就已经过时了,现在大多数年轻人都是直接通过手机来找工作。图片 找工作类的平台不但能扩大企业的招聘渠道,还能节省招聘的成本,方便求职者进…...
嵌入式学习-qt-Day3
嵌入式学习-qt-Day3 一、思维导图 二、作业 完善对话框,点击登录对话框,如果账号和密码匹配,则弹出信息对话框,给出提示”登录成功“,提供一个Ok按钮,用户点击Ok后,关闭登录界面,跳…...
零基础到高级:Android音视频开发技能路径规划
音视频开发趋势 Android音视频开发领域目前正处于一个高速发展的阶段,主要趋势如下: 超高清视频:4K视频亚毫米级显示清晰,更加逼真,为开发更加逼真的虚拟现实应用提供了基础。AI技术:自适应码率控制、视频…...
阿里云香港轻量应用服务器网络线路cn2?
阿里云香港轻量应用服务器是什么线路?不是cn2。 阿里云香港轻量服务器是cn2吗?香港轻量服务器不是cn2。阿腾云atengyun.com正好有一台阿里云轻量应用服务器,通过mtr traceroute测试了一下,最后一跳是202.97开头的ip,1…...
python中websockets与主线程传递参数
目录 一、子线程创建websockets服务端接收客户端数据 二、主线程内启动子线程接收并处理数据 一、子线程创建websockets服务端接收客户端数据并存入队列 发送的消息客户端与服务端统一,多种消息加入判断的标签 服务端:web_server.py import asynci…...
js谐音梗创意小游戏《望子成龙》
🌻 前言 龙年到来,祥瑞满天。愿您如龙般矫健,事业腾飞;如龙鳞闪耀,生活美满。祝您龙年大吉,万事如意! 龙年伊始,我给各位设计了一款原创的小游戏,话不多说,直…...
第十篇:node处理404和服务器错误
🎬 江城开朗的豌豆:个人主页 🔥 个人专栏 :《 VUE 》 《 javaScript 》 📝 个人网站 :《 江城开朗的豌豆🫛 》 ⛺️ 生活的理想,就是为了理想的生活 ! 目录</...
左右互博。
链接:登录—专业IT笔试面试备考平台_牛客网 来源:牛客网 讨厌鬼在和小甜妹在玩石头游戏。 游戏一开始有 nnn 堆石子,第 iii 堆石子,有 aia_iai 个石子。两人轮流进行游戏。 轮到某个人时,这个人先选数量为 x(x&…...
android通过广播打印ram使用信息
在内存非常吃紧的情况下,android设备会开始kill部分非系统进程甚至系统进程来保证基本的系统运行。在这种情况下如何获取设备过去某段时间的ram使用情况至关重要。 通过开发者模式中的“内存”可以完美得知设备内存使用信息。 我们可以通过此途径,设计一…...
内存管理——线性内存,进程空间
低2G为进程空间 开始地址结束地址大小属性00xFFFFF1M保留0x1000000x102FFF栈不固定位置、大小0x1030000x143FFF堆不固定位置、大小0x400000主程序文件不固定位置、大小加载dll不固定位置、大小0x7ffdd000TIB位置,大小编译时固定0x7FFFE000系统与用户共享数据块位置…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
