代码随想录算法训练营Day46|LC139 单词拆分

一句话总结:完全背包!

原题链接:139 单词拆分

动态规划之完全背包五部曲:

  1. 确定dp数组与下标含义:表示字符串长度为i时,dp[i] == true 的话,可以拆分为一个或多个在字典中出现的单词。
  2. 确定递归公式。当且仅当同时满足dp[j] == true && set.contains(substr(j ,i)),dp[i] = true;
  3. 动规数组的初始化。从递推公式可以看出dp[0] 必须为true,否则后面所有的dp[i]都将为false。
  4. 递推的遍历顺序。因为字符串的字符存在顺序,因此求的是排列数,所以遍历顺序为:外层循环遍历背包容量,内层循环遍历物品。由此4步即可确定整体代码如下。
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i && !dp[i]; j++) {
                if (set.contains(s.substring(j, i)) && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/521080.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C++相关概念和易错语法(4)(构造函数、析构函数)

一、构造函数 1.实现的功能&#xff1a;实例化对象的时候默认自动调用&#xff0c;相当于初始化。 条件&#xff1a;在书写时要满足构造函数的规范&#xff08;函数名 类名&#xff0c;不写返回值&#xff0c;也没有返回值&#xff09;&#xff0c;可以用inline来修饰。 2.自…

Microsoft Edge浏览器设置之后就很牛逼了

1.移除多余的广告 首先我们要先下载Microsoft Edge浏览器浏览器 然后在设置中先打开扩展,安装一个神奇的去广告插件 打开Edge 加载项 直接搜adguard 广告拦截器,直接获取就可以安装了,由于我已经安装过了,所以就是显示的删除。 2.解除网页复制限制 直接在扩展中安装sim…

Toyota Programming Contest 2024#4(AtCoder Beginner Contest 348)(A~D)

A - Penalty Kick i,1~N。如果 i 是 3 的倍数输出x&#xff0c;否则输出o #include <bits/stdc.h> //#define int long long #define per(i,j,k) for(int (i)(j);(i)<(k);(i)) #define rep(i,j,k) for(int (i)(j);(i)>(k);--(i)) #define debug(a) cout<<#…

HTTP详解及代码实现

HTTP详解及代码实现 HTTP超文本传输协议 URL简述状态码常见的状态码 请求方法请求报文响应报文HTTP常见的HeaderHTTP服务器代码 HTTP HTTP的也称为超文本传输协议。解释HTTP我们可以将其分为三个部分来解释&#xff1a;超文本&#xff0c;传输&#xff0c;协议。 超文本 加粗样…

开源 _ 新一代Android 性能监控框架Rabbit

最终扫描结果会展示如下: 点击右上角导出按钮可以把扫描结果以json的形式导出到SD卡中。 网络日志监控 rabbit可以记录网络请求日志并方便的查看返回的json数据: 卡顿日志监控 rabbit通过Choreographer来检测主线程的运行情况,并异步采集主线程堆栈来还原卡顿现场。 对于下…

总包不足80w的高龄Android程序员,被面试官diss混得太差,网友狂吐槽……

有网友直言&#xff1a;90%的人一辈子一年也拿不到80万 有网友分析到&#xff1a;看面试情况&#xff0c;没什么希望就直接其实我觉得30岁年薪低于1000万的都是loser&#xff0c;你我都是 有网友说&#xff1a;这几年互联网行业极大发展&#xff0c;让互联网行业成为了明星行…

2_6.Linux高级存储管理

##1.逻辑卷## pv ##物理卷 被处理过的物理分区 pe ##物理扩展 设定存储最小单元 vg ##物理卷组 捆绑pv到一个组中 lv ##逻辑卷 分配最终的使用设备 监控建立过程&#xff1a; watch -n 1 "pvs;echo ;vgs;echo ;lvs;echo ;df -h /weixindata" &#xff08;1&#xf…

合理早餐选择,稳定糖尿病血糖。

对于糖尿病患者来说&#xff0c;饮食管理是治疗的重要一环。不合理的早餐选择会导致血糖的波动。很多糖尿病朋友按时吃药&#xff0c;但是血糖就是稳定不住&#xff0c;之前看过一个例子&#xff0c;北京崇文门医院朱学敏主任接诊过一个患者&#xff0c;那个患者按时吃药&#…

C++设计模式:装饰器模式(四)

1、定义与动机 装饰器模式定义&#xff1a;动态&#xff08;组合&#xff09;地给一个对象增加一些额外的职责。就增加功能而言&#xff0c;Decorator模式比生成子类&#xff08;继承&#xff09;更为灵活&#xff08;消除重复代码 & 减少子类个数&#xff09;。 在某些情…

ARM体系结构

阅读引言&#xff1a; arm架构处理器的基本知识已在上一篇文章中描述过了&#xff0c; 本文将会从arm的存储模型、异常机制、工作模式、指令集、流水线、arm的寄存器组织方面去描述。 目录 一、ARM处理器概论 1.指令集概述 2.指令分类 3.编译流程 二、ARM的存储模型 1.AR…

电商技术揭秘七:搜索引擎中的SEO关键词策略与内容优化技术

文章目录 引言一、关键词策略1.1 关键词研究与选择1. 确定目标受众2. 使用关键词研究工具3. 分析搜索量和竞争程度4. 考虑长尾关键词5. 关键词的商业意图6. 创建关键词列表7. 持续监控和调整 1.2 关键词布局与密度1. 关键词自然分布2. 标题标签的使用3. 首次段落的重要性4. 关键…

C# 分布式自增ID算法snowflake(雪花算法)

文章目录 1. 概述2. 结构3. 代码3.1 IdWorker.cs3.2 IdWorkerTest.cs (测试) 1. 概述 分布式系统中&#xff0c;有一些需要使用全局唯一ID的场景&#xff0c;这种时候为了防止ID冲突可以使用36位的UUID&#xff0c;但是UUID有一些缺点&#xff0c;首先他相对比较长&#xff0c…

pyside6怎么使用Qt Designer设计自定义组件

第一步&#xff0c;新建一个自定义组件的python文件 from PySide6.QtWidgets import QPlainTextEdit from PySide6.QtCore import Signal,Qtclass CustomPlainTextEdit(QPlainTextEdit):enterPressed Signal(str)def __init__(self, parentNone):super().__init__(parent)def…

Vue+node.js蔬菜水果农产品网上商城管理系统

用户能够及时掌握最新的数据&#xff0c;并能有效地提升用户的服务水平。本制度的优势在于&#xff1a; &#xff08;1&#xff09;该系统将蔬菜信息及时地提供给使用者。使用者可以在任何时候登陆该网站查询相关资讯&#xff0c;所有资讯均真实可信&#xff0c;并严肃处理各项…

161 Linux C++ 通讯架构实战15,线程池代码分析

线程池应该使用的地方 和 epoll 技术结合 线程池代码处理数据的地方。 线程池分析&#xff1a; 线程池代码1 threadpool_create //Tencent8888 start threadpool_create函数的目的初始化线程池&#xff0c;对应的struct是 threadpool_t /* 1.先malloc整个线程池的大小 2.这里…

牛客 2024春招冲刺题单 ONT98 牛牛猜节点【中等 斐波那契数列 Java,Go,PHP】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/6a3dfb5be4544381908529dc678ca6dd 思路 斐波那契数列参考答案Java import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定&#xff0c;请勿修改&#xff0c;直接返回方法规…

Unity与CocosCreator对比学习二

一、锚点与适配 1.在Creator中 适配通过锚点、位置和Widget达到适配目的&#xff1b;锚点是节点在其父节点坐标系中坐标对其点&#xff0c;其x,y范围在[0, 1]之间&#xff1b; 锚点为(0, 0)时在节点自身的左下角&#xff0c;节点坐标指其左下角在父节点中的坐标&#xff1b;锚…

贪心算法|53.最大子序和

力扣题目链接 class Solution { public:int maxSubArray(vector<int>& nums) {int result INT32_MIN;int count 0;for (int i 0; i < nums.size(); i) {count nums[i];if (count > result) {result count;}if (count < 0) count 0;}return result;} …

[AIGC] Spring Filter 过滤器详解

什么是Spring Filter 在Web应用中&#xff0c;Filter&#xff08;过滤器&#xff09;是在Java Servlet规范中的一种组件&#xff0c;它的主要目的是对HTTP请求或者响应进行处理。Spring Filter则是Spring框架对Java原生Filter的封装版本和扩展。 简单来说&#xff0c;Spring …

物联网实战--驱动篇之(二)Modbus协议

目录 一、modbus简介 二、功能码01、02 三、modbus解析 四、功能码03、04 五、功能码05 六、功能码06 七、功能码16 一、modbus简介 我们在网上查阅modbus的资料发现很多很杂&#xff0c;modbus-RTU ASCII TCP等等&#xff0c;还有跟PLC结合的&#xff0c;地址还分1开…