代码随想录算法训练营第四十六天| LeetCode139.单词拆分

一、LeetCode139.单词拆分

题目链接/文章讲解/视频讲解:https://programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.html

状态:已解决

1.思路 

        单词明显就是物品,字符串s明显就是背包,那么问题就变成了物品能不能把背包装满。

(1)确定dp数组以及下标的含义:

        dp[i]:字符串长度为i,dp[i]为true,代表长度为 i 的子串可以被单词组成。

(2)确定递推公式:

        对于dp[i],如果一个长为 wordDict[j].size() 的物品(单词)是s在[i-wordDict[j],i]这个范围内的子串,那么dp[i] = dp[j]的状态。

(3) 初始化dp数组:

        dp[0]表示如果字符串为空的话,说明出现在字典里。(实际题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况,那么dp[0]初始为true完全就是为了推导公式。)

        下标非0的dp[i]初始化为false,只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

(4)确定遍历顺序:

        题目中说是拆分为一个或多个在字典中出现的单词,所以这是完全背包。本题其实我们求的是排列数, 拿 s = "applepenapple", wordDict = ["apple", "pen"] 举例。"apple", "pen" 是物品,那么我们要求 物品的组合一定是 "apple" + "pen" + "apple" 才能组成 "applepenapple"。"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的,那么我们就是强调物品之间顺序。所以说,本题一定是 先遍历 背包,再遍历物品。且内外层都是从前往后遍历。

(5)举例推导dp:

以输入: s = "leetcode", wordDict = ["leet", "code"]为例,dp状态如图:

dp[s.size()]就是最终结果。

2.代码实现 

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {vector<bool> dp(s.size()+1,false);dp[0] = true;for(int i=0;i<=s.size();i++){for(int j=0;j<wordDict.size();j++){if(wordDict[j].size() <= i){string word = s.substr(i-wordDict[j].size(),wordDict[j].size());if(!dp[i] && word == wordDict[j]){dp[i] = dp[i-wordDict[j].size()];}}}}//for(int i=0;i<=s.size();i++) cout<<dp[i]<<" ";return dp[s.size()];}
};

时间复杂度:O(n^3) :求子串是一个O(n)的复杂度

空间复杂度:O(n)

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Jmeter之Beanshell详解

一、 Beanshell概念 Beanshell: BeanShell是一种完全符合Java语法规范的脚本语言,并且又拥有自己的一些语法和方法;BeanShell是一种松散类型的脚本语言(这点和JS类似);BeanShell是用Java写成的,一个小型的、免费的、可以下载的、嵌入式的Java源代码解释器,具有对象脚本语言特性…

【项目实战】基于高并发服务器的搜索引擎

【项目实战】基于高并发服务器的搜索引擎 目录 【项目实战】基于高并发服务器的搜索引擎搜索引擎部分代码index.htmlindex.hpplog.hppparser.cc&#xff08;用于对网页的html文件切分且存储索引关系&#xff09;searcher.hpputil.hpphttp_server.cc&#xff08;用于启动服务器和…

plsql 新建sql窗口 初始化慢的问题

问题描述&#xff1a; 新建sql窗口当sql语句多的情况下初始化很慢。 解决方法&#xff1a; 采用导入表的方式。 具体方式 工具->导入表->sql插入。 使用命令窗口 导入文件&#xff0c;然后点击导入按钮。

SpringBoot学习之SpringBoot3集成OpenApi(三十八)

Springboot升级到Springboot3以后,就彻底放弃了对之前swagger的支持,转而重新支持最新的OpenApi,今天我们通过一个实例初步看看OpenApi和Swagger之间的区别. 一、POM依赖 我的POM文件如下,仅作参考: <?xml version="1.0" encoding="UTF-8"?>…

社交巨头与去中心化:解析Facebook在区块链的角色

在数字化时代&#xff0c;社交媒体已经成为人们日常生活中不可或缺的一部分。作为全球最大的社交媒体平台&#xff0c;Facebook 在社交领域的影响力无可置疑。然而&#xff0c;随着区块链技术的崛起&#xff0c;Facebook 也开始探索如何将这一技术应用于其平台&#xff0c;以适…

SpringMVC 源码剖析

SpringMVC 源码剖析 0 从源码角度分析SpringMVC执行流程 // 前端控制器&#xff0c;SpringMVC最核心的类 public class DispatcherServlet extends FrameworkServlet {// 前端控制器最核心的方法&#xff0c;这个方法是负责处理请求的&#xff0c;一次请求&#xff0c;调用一次…

Unity类银河恶魔城学习记录15-5,6 p157 Audio time limiter p158 Area sound

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili​​ AreaSound.cs using System.Collections; using System.Collections.G…

精益生产咨询公司能够为浙江企业带来哪些帮助?

精益生产&#xff0c;起源于丰田生产方式&#xff0c;强调以最少的资源投入获得最大的运营效益。其核心思想包括消除浪费、持续改进、员工参与和顾客至上。在浙江这片民营经济繁荣的土地上&#xff0c;众多企业敏锐地捕捉到了精益生产带来的巨大潜力&#xff0c;积极寻求与咨询…

SpringBoot学习之Kafka发送消费消息入门实例(三十五)

使用Kafka之前需要先启动fKafka,如何下载安装启动kafka请先参考本篇文章的前两篇: 《SpringBoot学习之Kafka下载安装和启动【Windows版本】(三十四)》 《SpringBoot学习之Kafka下载安装和启动【Mac版本】(三十三)》 一、POM依赖 1、加入kafka依赖 2、我的整个POM代码…

分类预测 | Matlab实现SCSO-SVM沙猫群优化算法优化支持向量机多特征分类预测

分类预测 | Matlab实现SCSO-SVM沙猫群优化算法优化支持向量机多特征分类预测 目录 分类预测 | Matlab实现SCSO-SVM沙猫群优化算法优化支持向量机多特征分类预测分类效果基本描述程序设计参考资料 分类效果 基本描述 1.Matlab实现SCSO-SVM沙猫群优化算法优化支持向量机多特征分类…

怎么通过Javascript脚本实现远程控制一路开关

怎么通过Javascript脚本实现远程控制一路开关呢&#xff1f; 本文描述了使用Javascript脚本调用HTTP接口&#xff0c;实现控制一路开关。一路开关可控制一路照明、排风扇等电器。 可选用产品&#xff1a;可根据实际场景需求&#xff0c;选择对应的规格 序号设备名称1智能WiFi…

Spark-机器学习(3)回归学习之线性回归

在之前的文章中&#xff0c;我们了解我们的机器学习&#xff0c;了解我们spark机器学习中的特征提取和我们的tf-idf&#xff0c;word2vec算法。想了解的朋友可以查看这篇文章。同时&#xff0c;希望我的文章能帮助到你&#xff0c;如果觉得我的文章写的不错&#xff0c;请留下你…

从头开始构建自己的 GPT 大型语言模型

图片来源&#xff1a; Tatev Aslanyan 一、说明 我们将使用 PyTorch 从头开始构建生成式 AI、大型语言模型——包括嵌入、位置编码、多头自注意、残差连接、层归一化&#xff0c;Baby GPT 是一个探索性项目&#xff0c;旨在逐步构建类似 GPT 的语言模型。在这个项目中&#xff…

java 学习一

jdk下载地址 配置环境变量

网络安全实训Day24(End)

写在前面 并没有完整上完四个星期&#xff0c;老师已经趁着清明节假期的东风跑掉了。可以很明显地看出这次持续了“四个星期”实训的知识体系并不完整&#xff0c;内容也只能算是一次基础的“复习”。更多的内容还是靠自己继续自学吧。 网络空间安全实训-渗透测试 文件包含攻击…

机器人系统开发ros2-基础实践01-学会自定义一个机器人动作aciton实体类

您之前在了解操作教程中了解了action 。与其他通信类型及其各自的接口&#xff08;主题/消息和服务/srv&#xff09;一样&#xff0c;您也可以在包中自定义操作。本教程向您展示如何定义和构建可与您将在下一个教程中编写的action服务器和action 客户端一起使用的操作。 需要理…

RabbitMQ发布确认和消息回退(6)

概念 发布确认原理 生产者将信道设置成 confirm 模式&#xff0c;一旦信道进入 confirm 模式&#xff0c;所有在该信道上面发布的消息都将会被指派一个唯一的 ID(从 1 开始)&#xff0c;一旦消息被投递到所有匹配的队列之后&#xff0c;broker就会发送一个确认给生产者(包含消…

GDPU 竞赛技能实践 天码行空9

1. 埃式筛法 求区间[2, n]内所有的素数对 &#x1f496; Main.java import java.util.Scanner;public class Main {static int N (int) 1e8, cnt 0;static int[] p new int[N];static boolean[] st new boolean[N];public static void main(String[] args){Scanner sc …

(mac)Promethues监控之mysqld_exporter(MySQL监控)

搭建Mysqld_exporterPrometheusGrafana监控系统 普罗米修斯是后端数据监控平台&#xff0c;通过Mysqld_exporter收集mysql数据&#xff0c;Grafana将数据用图形的方式展示出来 前提&#xff1a;已安装grafana和promethues 1.下载安装Mysql &#xff08;1&#xff09;启动MySQL…

一个联合均值与方差模型的R包——dglm

目录 一、引言二、包的安装与载入三、模拟例子3.1 数据生成3.2 数据查看3.3 模型估计参数 一、引言 在 R 语言中&#xff0c;dglm 包是用于拟合双参数广义线性模型&#xff08;Double Generalized Linear Models&#xff0c;简称 DGLMs&#xff09;的一个工具。这类模型允许同…