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系统与用户共享数据块位置…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...
