【LeetCode】139. 单词拆分
139. 单词拆分(中等)
-
思路
- 首先将大问题分解成小问题:
- 前 i 个字符的子串,能否分解成单词;
- 剩余子串,是否为单个单词;
- 动态规划的四个步骤:
-
确定 dp 数组以及下标的含义
dp[i] 表示 s 的前 i 位是否可以用 wordDict 中的单词表示。
-
确定递推公式
如果 dp[j] == true,且 [j, i] 这个区间的子串出现在字典里,那么 dp[i] 一定是true。
所以可以确定递推公式:
if([j,i] 这个区间的子串出现在字典里 && dp[j] == true) dp[i] = true;
-
dp 数组初始化
从递归公式中可以看出, dp[i] 的状态依靠 dp[j] 是否为 true,那么 dp[0] 就是递归的根基,令 dp[0] = true ,因为空字符串一定可以被表示;
-
确定遍历顺序
题目中说是拆分为一个或多个在字典中出现的单词,所以这是完全背包问题,需要讨论两层 for 循环的前后顺序。 本周小结!(动态规划系列五)
如果求组合数就是外层 for 循环遍历物品,内层 for 循环遍历背包;
如果求 排序数就是外层 for 循环遍历背包,内层 for 循环遍历物品。由于本题要求的是是否都出现过,因此对单词集合里的元素是组合还是排序,并不在意,那么本题使用哪一种方法都可以。
但本题存在特殊性,因为要求的是子串,所以最好是遍历背包放在外层循环,遍历物品放在内层循环。如果相反的话,需要将所有子串预先放在一个容器里,比较麻烦。
-
- 首先将大问题分解成小问题:
-
代码
class Solution { public:bool wordBreak(string s, vector<string>& wordDict) {int n = s.size();unordered_set<string> WordSet(wordDict.begin(), wordDict.end());vector<bool> dp(n+1, false);dp[0] = true; // 初始状态for(int i=1; i<=n; ++i){for(int j=0; j<=i; ++j){string word = s.substr(j, i-j); // (起始位置,长度)if(WordSet.find(word) != WordSet.end() && dp[j]){dp[i] = true;}}}return dp[n];} };
-
收获
- 总感觉之前做过类似的题,不过不是使用动态规划的解法。这道题完全没思路,找了很多题解才明白,最后参考的是代码随想录的解法。
相关文章:
【LeetCode】139. 单词拆分
139. 单词拆分(中等) 思路 首先将大问题分解成小问题: 前 i 个字符的子串,能否分解成单词;剩余子串,是否为单个单词; 动态规划的四个步骤: 确定 dp 数组以及下标的含义 dp[i] 表示 s…...
【三维重建】NeRF原理+代码讲解
文章目录 一、技术原理1.概览2.基于神经辐射场(Neural Radiance Field)的体素渲染算法3.体素渲染算法4.位置信息编码(Positional encoding)5.多层级体素采样 二、代码讲解1.数据读入2.创建nerf1.计算焦距focal与其他设置2.get_emb…...
IntelliJ IDEA 社区版2021.3配置SpringBoot项目详细教程及错误解决方法
目录 一、SpringBoot的定义 二、Spring Boot 优点 三、创建一个springboot的项目 四、使用IDEA创建SpringBoot失败案例 一、SpringBoot的定义 Spring 的诞⽣是为了简化 Java 程序的开发的,⽽ Spring Boot 的诞⽣是为了简化 Spring 程序开发的。 Spring Boot 翻…...
Qt中QDebug的使用
QDebug类为调试信息(debugging information)提供输出流。它的声明在<QDebug>中,实现在Core模块中。将调试或跟踪信息(debugging or tracing information)写出到device, file, string or console时都会使用QDebug。 此类的成员函数参考:https://doc…...
vue使用路由的query配置项时如何清除地址栏的参数
写vue项目时,如果想通过路由的query配置项把参数从一个组件传到另一个组件,但是又不希望?idxxx显示在地址栏(如:http://localhost:8080/test?idxxx的?idxxx),该怎么做: 举一个案例࿱…...
Redis-列表(List)
Redis列表(List) 介绍 单键多值Redis 列表是简单的字符串列表,按照插入顺序排序。你可以添加一个元素到列表的头部(左边)或者尾部(右边)它的底层实际是个双向链表,对两端的操作性能很高,通过索…...
ripro主题修改教程-首页搜索框美化教程
先看效果图: 我们来看怎么实现: 1、找到wp-content/themes/ripro/assets/css/diy.css并将下面的内容整体复制进去并保存 /*首页搜索框*/ .bgcolor-fff {background-color: #fff; } .row,.navbar .menu-item-mega>.sub-menu{margin-left:-10px;margin-right:-10px;} .home…...
写作业用白光还是暖光?盘点色温4000K的护眼台灯
台灯的白光或者暖光指的是台灯的色温,低色温的光线看起来发黄发红,高色温的光线发白发蓝。 如果灯光的光源是高品质光源,本身没有蓝光问题,那么色温的选择对护眼的影响是比较少的,更多的是对人学习工作状态,…...
Java时间类(一)-- SimpleDateFormat类
目录 1. SimpleDateFormat的构造方法: 时间模式字母: 2. SimpleDateFormat的常用方法: “工欲善其事,必先利其器”。学习时间类之前,需要先学习SimpleDateFormat类。 java.text.SimpleDateFormat类是以与语言环境有关的方式来格式...
07 Kubernetes 网络与服务管理
课件 Kubernetes Service是一个抽象层,用于定义一组Pod的访问方式和访问策略,其作用是将一组Pod封装成一个服务,提供一个稳定的虚拟IP地址和端口号,以便于其他应用程序或服务进行访问。 以下是Kubernetes Service YAML配置文件的…...
并发编程之Atomic原子操作类
基本类型:AtomicInteger、AtomicBoolean、AtomicLong 引用类型:AtomicReference、AtomicMarkableReference、AtomicStampedReference 数组类型:AtomicIntegerArray、AtomicLongArray、AtomicReferenceArray 对象属性原子修改器:…...
管家婆辉煌Ⅱ 13.32版安装方法
因管家婆辉煌版已经长期不更新,现已经出现蓝屏的问题,故此新开此贴,慢慢更新安装方法。 首先管家婆下载地址:http://www.grasp.com.cn/download.aspx?id116 先安装sql server 2008 下载后,运行安装,请注…...
常见的接口优化技巧思路
一、背景 针对老项目,去年做了许多降本增效的事情,其中发现最多的就是接口耗时过长的问题,就集中搞了一次接口性能优化。本文将给小伙伴们分享一下接口优化的通用方案。 二、接口优化方案总结 1.批处理 批量思想:批量操作数据…...
【Java EE】-使用Fiddler抓包以及HTTP的报文格式
作者:学Java的冬瓜 博客主页:☀冬瓜的主页🌙 专栏:【JavaEE】 分享: 在满园弥漫的沉静的光芒之前,一个人更容易看到时间,并看到自己的身影。——史铁生《我与地坛》 主要内容:使用FIddler抓包的…...
Java异步编程
Java异步编程 1、什么是java异步编程2、异步编程有什么作用3、异步编程常用于哪些业务4、异步编程的方式5、Async异步调用Async简介 1、什么是java异步编程 Java异步编程是一种处理并发问题的技术,它可以在执行耗时操作的同时,不阻塞主线程,…...
C++类与对象(二)——构造函数与析构函数
文章目录 一.类的默认6个成员函数二.构造函数1.引例2.构造函数的概念及特性 三.析构函数😋析构函数的特性 前言: 上篇文章初步认识了类以及类的相关知识,本篇将继续深入学习类与对象——类的默认6个成员函数: 一.类的默认6个成员函…...
c++标准模板(STL)(std::array)(四)
定义于头文件 <array> template< class T, std::size_t N > struct array;(C11 起) std::array 是封装固定大小数组的容器。 此容器是一个聚合类型,其语义等同于保有一个 C 风格数组 T[N] 作为其唯一非静态数据成员的结构体。不同于 C 风格数…...
vue3计算属性
计算属性 模板中的表达式虽然方便,但也只能用来做简单的操作。如果在模板中写太多逻辑,会让模板变得臃肿,难以维护。推荐使用计算属性来描述依赖响应式状态的复杂逻辑 基础示例 不够好的示例 模板中使用了表达式,不够直观&…...
Java 中的访问修饰符有哪些(九)
Java 中的访问修饰符用于限制类、接口、字段和方法的访问范围,它们分别表示不同的访问控制级别。Java 中共有四种访问修饰符:public、protected、default 和 private。 public public 是最开放的访问修饰符,用于指定公共访问级别。被 publi…...
HR员工管理的三重境界:管事、管人、管心
在一个公司里,员工来来往往是常态,虽说我们不能替他们决定,但是一定是与公司的管理者有一定的关系。马云曾经说过:“一个员工离职,不外乎两种原因,一是钱没给到位;二是心里委屈了”。一句话就是…...
延迟队列与SpringBoot实战
延迟队列与SpringBoot实战 概念 延时队列,队列内部是有序的,最重要的特性就体现在它的延时属性上,延时队列中的元素是希望在指定时间到了以后或之前取出和处理,简单来说,延时队列就是用来存放需要在指定时间被处理的元素的队列 …...
【算法】九键输入法
题目: 输入数字字符串, 输出这串字符对应的九键输入法有可能出现的所有情况 算法: 定义了一个全局变量 g_numStr,其中存储了每个数字对应的字母。定义了一个递归函数 str_combine,用于将每个数字对应的字母进行组合。str_combin…...
jvm之类加载器
写在前面 当我们通过javac命令将java源代码编译为Java字节码后,必须通过类加载器将其加载到jvm中才能运行,所以类加载器是jvm中非常重要的一个组成部分,本文我们就一起来看下吧! 1:类的生命周期 类的生命周期如下图…...
Chapter4:频率响应法(上)
第四章:频率响应法 Exercise4.1 已知微分网络和积分网络电路图如下图所示,求网络的频率特性。 解: 【图 ( a ) ({\rm a}) (a)微分网络】 由微分网络电路图可得:...
【6. 激光雷达接入ROS】
欢迎大家阅读2345VOR的博客【6. 激光雷达接入ROS】🥳🥳🥳 2345VOR鹏鹏主页: 已获得CSDN《嵌入式领域优质创作者》称号👻👻👻,座右铭:脚踏实地,仰望星空&#…...
Java 基础进阶篇(三)—— 面向对象的三大特征之二:继承
文章目录 一、继承概述二、内存运行原理 ★三、继承的特点四、继承后:成员变量和方法的访问特点五、继承后:方法重写六、继承后:子类构造器的特点七、继承后:子类构造器访问父类有参构造器八、this、super 总结 一、继承概述 Jav…...
[angstromctf 2023] 部分
这个比赛打了个开头就放弃了,最近放弃的比较多,国外的网太慢,国内的题太难。 Crypto ranch 这题直接给出密文这提示 rtkw{cf0bj_czbv_nvcc_y4mv_kf_kip_re0kyvi_uivjj1ex_5vw89s3r44901831} Caesar dressing is so 44 BC... 然后是加密程序…...
死信队列
死信队列 死信的概念 先从概念解释上搞清楚这个定义,死信,顾名思义就是无法被消费的消息,字面意思可以这样理解,一般来说,producer 将消息投递到 broker 或者直接到queue 里了,consumer 从 queue 取出消息…...
基于YOLOv5的目标检测系统详解(附MATLAB GUI版代码)
摘要:本文重点介绍了基于YOLOv5目标检测系统的MATLAB实现,用于智能检测物体种类并记录和保存结果,对各种物体检测结果可视化,提高目标识别的便捷性和准确性。本文详细阐述了目标检测系统的原理,并给出MATLAB的实现代码…...
使用ChatGPT工具阅读文献的实战教程
大家好,我是herosunly。985院校硕士毕业,现担任算法研究员一职,热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名,CCF比赛第二名,科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的见解。曾经辅导过若干个非计算机专业的学生进入到算法…...
网站打开出现建设中/搜索引擎优化的简称是
虚拟化由于其带来的维护费用的大幅降低而受到追捧,如能减少服务器占用空间,降低购买软硬件设备的成本,大幅度提高系统的利用率。然而对其安全问题,人们也一直在争论不休,一方观点认为虚拟化技术能有效提升系统的安全性…...
网站制作价格东莞/b2b外链代发
来源:Talkwithtrend ID:Talkwithtrend 在此收集的支付宝的系统架构图包含:清算、客服、处理、资金、财务等等,由于资料年限限制,仅供参考,但基本架构相信还是变化不大的。作为支付行业的龙头,…...
泰安做网站公司哪家好/seo顾问服务 乐云践新专家
目录注释变量和常量标识符的命名规范字符串输出键盘输入数据类型整数类型浮点类型字符类型布尔类型Unit类型,Null类型和Nothing类型(重点)Unit类型Null类型Nothing类型类型转换数值类型自动转换强制类型转换注释 scala的注释的使用跟JAVA是一…...
临汾做网站的公司/哈尔滨优化网站公司
Offer_day04_53 - I. 在排序数组中查找数字 I 统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums [5,7,7,8,8,10], target 8 输出: 2 示例 2: 输入: nums [5,7,7,8,8,10], target 6 输出: 0 提示: 0 < nums.length < 105 -109 < nums[i] …...
平谷区住房城乡建设委官方网站/餐饮营销引流都有什么方法
一、准备工作 Eureka通过运行多个实例,使其更具有高可用性。事实上,这是它默认的熟性,你需要做的就是给对等的实例一个合法的关联serviceurl 二、改造工作 在eureka-server工程中resources文件夹下,创建配置文件application-pe…...
wordpress 中文付费主题/seo网页推广
cellfun函数 n A{Hello, MATLAB, I love MATLAB, MATLAB is powerful, MATLAB is the language of technical computer} ;试统计A中每个元胞......函数语法为: Bcellfun(fun,A) ; fun 表示实现运算的 匿名函数或函数句柄,A是被实施运算的元胞数组。cellfun函数更详 细的使用说明…...