力扣-139单词拆分
力扣-139单词拆分
1、题目
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例 1:
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
2、分析
- 首先看都这个问题,第一个想到的还是回溯,但是现在动归训练了这几天,也可以看出这是个完全背包问题,因为可以重复使用。
- dp[i]就表示长度为i时,在0-i区间这个截取字符串是否满足wordDict字符串构成,若构成则值为true,反之为false;
- 其次,因为组成的是个字符串单词,是有顺序的,所以采用排列方式,即外循环i为背包容量,即s字符串长度,外循环j,当j<i,即构成j-i这个区间的字符串,可完成判断是否在wordDict中存在,若存在,即dp[i]=true,若不存在,还是false不变。这样,我们在判断是否存在时,就可以通过前面的dp[j]是否是true,如果是true,代表前面刚好放入了一个wordDict字符串,结尾在j下标,后面我们才能再放入一个完整的新wordDict里面的字符串。
- 这里我们可以利用hashset存wordDict值,或者在循环的时候进行截取即可。
- 编写代码。
3、代码及注释
class Solution {public boolean wordBreak(String s, List<String> wordDict) {// 1.完全背包,判断情况:排列// 2.dp[i]表示到i下标前能够添加成功wordDict字符串,为trueboolean[] dp = new boolean[s.length() + 1];Set<String> set = new HashSet<>(wordDict);dp[0] = true;for (int i = 1; i <= s.length(); i++){for (int j = 0; j < i; j++){// 3.wordDict是否存在,是否在前面j的时候是放入完整的一个字符串if (set.contains(s.substring(j, i)) && dp[j]){dp[i] = true;}}}return dp[s.length()];}
}
4、练习
力扣题目链接:https://leetcode.cn/problems/word-break/
相关文章:
力扣-139单词拆分
力扣-139单词拆分 1、题目 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 示例 1: 输入: s "…...
图机器学习-图神经网络
图神经网络 前面讲了图机器学习的一些传统方法,现在正式进入到课程的核心部分:图神经网络。 Design of GNN 那么图神经网络和我们之前接触的一些深度神经网络有什么不同呢? 对于别的类型的神经网络,往往我们都是处理一些类似网…...
配置Airbyte资源限制
资源限制有三种不同的级别配置:Instance-wide - 应用到Airbyte实例创建的Sync Job的所有容器上。Connector-specific - 应用到Airbyte实例创建的Sync Job的所有指定类型连接器的容器上Connection-specific - 应用到Airbyte实例创建的Sync Job的所有指定管道的容器上…...
python实现PCA降维画分类散点图并标出95%的置信区间
此代码以数据集鸢尾花为例,对其使用PCA降维后,绘制了三个类别的样本点和对应的置信圆(即椭圆)。先放效果图。 下面是完整代码: from matplotlib.patches import Ellipsedef plot_point_cov(points, nstd3, axNone, **…...
Mysql高级之索引结构详解
Mysql的索引详解1.索引定义2.索引结构2.1数据结构分析2.1.1熟知的数据结构2.1.2分析为什么这么多的数据结构不全适用于索引结构2.2Hash结构2.3B tree结构3.索引分类3.1聚集索引(聚簇索引)3.2非聚集索引(稀疏索引)3.3联合索引3.4主…...
【线程-J.U.C】
Lock J.U.C最核心组件,Lock接口出现之前,多线程的并发安全只能由synchronized处理,但java5之后,Lock的出现可以解决synchronized的短板,更加灵活。 Lock本质上是一个接口,定义了释放锁(unlock&…...
docker布署spring boot jar包项目
目录docker 安装创建目录制作镜像启动容器查看日志docker 安装 Docker安装、详解与部署 创建目录 服务器中创建一个目录,存放项目jar包和Dockerfile 文件 mkdir /目录位置创建目录后创建Dockerfile文件,上传jar包到同一目录下 创建dockerfile vim Doc…...
极简Vue3教程--Pinia状态管理
Pinia(发音为/piːnjʌ/,如英语中的“peenya”)是最接近pia(西班牙语中的菠萝)的词;Pinia开始于大概2019年,最初是作为一个实验为Vue重新设计状态管理,让它用起来像组合式API&#x…...
常用的map转bean互转方法
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 常用的map转bean互转方法一、hutool工具类二、fastjson工具类三、beanutils_BeanUtils工具类 不太好用四、cglib BeanMap工具类 不太好用五、reflect 反射来玩 不太好玩六、I…...
2.4G收发一体芯片NRF24L01P跟国产软硬件兼容 SI24R1对比
超低功耗高性能 2.4GHz GFSK 无线收发器芯片Si24R1,软硬件兼容NRF24L01P. Si24R1 是一颗工作在 2.4GHz ISM 频段,专为低功耗无线场合设计,集成嵌入式ARQ 基带协议引擎的无线收发器芯片。工作频率范围为 2400MHz-2525MHz,共有 126个…...
设计模式之七大原则(一)——单一职责原则、开放-关闭原则
目录一、设计模式的目的二、设计模式的七大原则1.单一职责原则2.开放-关闭原则一、设计模式的目的 设计模式的目的是为了提高代码重用性、可读性、可扩展性、可靠性,使得程序呈现出高内聚、低耦合的特性。 代码重用性(相同功能的代码,不用多…...
C++ set、unordered_set、multiset它们之间的区别与一些使用方法(不断更新)
set、unordered_set、multiset是什么?以及它们之间的区别 首先,它们三个都是C标准库提供的关联容器中的一种。只不过set、multiset容器是有序的,而unordered_set容器是无序的 std::set 是 C 标准库中的一个容器,其存储的元素按设…...
hadoop调优
hadoop调优 1 HDFS核心参数 1.1 NameNode内存生产配置 1.1.1 NameNode内存计算 每个文件块大概占用150byte,如果一台服务器128G,能存储的文件块如下 128 (G)* 1024(MB) * 1024(KB) * 1024(Byte) / 150 Byte 9.1 亿 1.1.2 Hadoop2.x 在Hadoop2.x中…...
EM@三角函数诱导公式
文章目录诱导公式单位圆坐标和三角函数记忆口诀符号看象限奇变偶不变例常用诱导公式🎈常用部分(5对)倒数关系六种三角函数间的转换关系小结ReflectionsShifts and periodicity诱导公式 诱导公式 - 维基百科,自由的百科全书 (wikipedia.org) 单位圆坐标…...
是不是只能学IT互联网技术才有发展前途?
当然不是,三百六十行,行行出状元。 但我们需要认清一个现实是,我们正处于一个信息爆炸的时代,掌握紧跟潮流的技术,才可以让我们更自信地面对每天的生活,才有多余的精力、财力来享受生活。“人生在世&#…...
Linux 进程:exit和_exit的辨析
目录1.接口与函数2.缓冲区3.exit 与 _exit(1)_exit(2)exit这里来认识exit函数和 _exit接口 ,它们的作用是类似的,都是在调用后退出程序,可以在程序的任何地方调用。 1.接口与函数 exit函数和_exit接口,一个函数,一个…...
智能电子标签——商超版价签
2.1英寸TFT黑白电子价签 ★ 快速变价,高效运营 ★ 市场实用,布局物联网未来 ★ 更好客户体验 ★ 降低系统成本,具备竞争力 ★ 2.1英寸黑白红电子价签 ★ 电池低能耗,常规使用三年 ★ 穿透力强不慣障碍 ★ 2.4G载波&#x…...
计算机网络自检
1 计网体系结构 因特网结构: 计网三个组成成分: 工作方式-其中2个部分: 功能-两个子网: 5个XAN分别是: 传输技术,两者的主要区别: 4种基本网络拓扑结构: 3种交换技术: 协…...
DC真实数据都有哪些?Filecoin为DC数据存储的解决方案又是什么?
对于生活在数字时代的我们而言,数据或许就和平日呼吸的空气一样,已经不需要我们再去思考其概念。我们的日常生活中无时无刻都有数据的身影,日常的购物消费、出行、学习、记录,当我们每天生活有数字化加持的小区里,工作…...
解决vscode无法自动更新
一.前言 要在vscode里面安装插件,被提示版本不匹配,然后得更新,然后我发现我的'帮助'菜单栏下没有检查更新,然后我去&…...
SakuraLLM:二次元翻译的终极解决方案,完全离线的日中翻译大模型
SakuraLLM:二次元翻译的终极解决方案,完全离线的日中翻译大模型 【免费下载链接】Sakura-13B-Galgame 适配轻小说/Galgame的日中翻译大模型 项目地址: https://gitcode.com/gh_mirrors/sa/Sakura-13B-Galgame 如果你热爱日本轻小说、Galgame等二次…...
LED照明设计必看:TIR透镜在LightTools中的准直与均匀优化技巧
LED照明设计进阶:TIR透镜在LightTools中的高效准直与均匀优化实战 在LED照明设计领域,TIR(全内反射)透镜因其独特的光学特性已成为高端照明产品的核心组件。与传统的平凸透镜和反光杯相比,TIR透镜能够同时处理小角度和…...
前开发转行AI萨满:给大模型驱魔收费百万
在人工智能的狂潮中,一个看似荒诞的职业正在硅谷悄然兴起——AI萨满。他们不是巫师,而是精通软件测试的前开发者,用测试思维为大型语言模型“驱魔”,收费高达百万。本文将从软件测试的专业视角,揭秘这一转型背后的逻辑…...
STM32 USART串口调试避坑指南:从波特率配置到数据帧异常排查
STM32 USART串口调试避坑指南:从波特率配置到数据帧异常排查 在嵌入式开发中,USART串口通信是最基础却又最容易出问题的环节之一。许多开发者都曾经历过这样的场景:代码编译通过,硬件连接无误,但串口就是无法正常通信&…...
市场比较好的显示屏模块供货商哪家强
市场比较好的显示屏模块供货商推荐在显示屏模块市场,众多企业各展所长,为不同行业提供着优质的产品。以下为您介绍十家市场上表现出色的显示屏模块供货商:杭州斡能电子有限公司(杭州斡能) 杭州斡能始创于2008年10月&am…...
GESP5级C++考试语法知识(十一、递归算法(一))
🌟 第一章:什么是递归?(“套娃小精灵”的故事)1、🎯 想象一个魔法世界:有一个小精灵,它不会做复杂的事情,但它有一个绝招:👉 遇到问题,…...
ZeroOmega代理规则引擎:构建智能化网络访问策略
ZeroOmega代理规则引擎:构建智能化网络访问策略 【免费下载链接】ZeroOmega Manage and switch between multiple proxies quickly & easily. 项目地址: https://gitcode.com/gh_mirrors/ze/ZeroOmega 在数字化生活中,我们每天都在与各种网络…...
工业协议通信开发实战:lib60870开源库完全指南
工业协议通信开发实战:lib60870开源库完全指南 【免费下载链接】lib60870 Official repository for lib60870 an implementation of the IEC 60870-5-101/104 protocol 项目地址: https://gitcode.com/gh_mirrors/li/lib60870 在工业自动化领域,设…...
java毕业设计基于springboot铜仁一中学生成绩管理系统
前言 铜仁一中学生成绩管理系统是基于Java和Spring Boot框架开发的,目的是高效管理学生的成绩信息,为学校教学管理提供便利。通过该系统,教师可以方便地录入学生的各科考试成绩,学生和教师能够根据不同条件查询成绩,系…...
Logisim-evolution完全指南:跨平台安装与配置实战
Logisim-evolution完全指南:跨平台安装与配置实战 【免费下载链接】logisim-evolution Digital logic design tool and simulator 项目地址: https://gitcode.com/gh_mirrors/lo/logisim-evolution 准备阶段:从零开始的环境搭建 1.1 认识Logisim…...
