当前位置: 首页 > news >正文

【动态规划】139. 单词拆分

139. 单词拆分

难度:中等
力扣地址:https://leetcode.cn/problems/word-break/description/

在这里插入图片描述

问题描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

示例 1:

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

示例 2:

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。
注意,你可以重复使用字典中的单词。

示例 3:

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

提示:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅由小写英文字母组成 wordDict 中的所有字符串 互不相同

问题分析

套公式(完全背包)之前,需要先回顾一下完全背包问题,并结合本道题内容进行适配。

在这里插入图片描述
接着我们回顾一下完全背包问题的求解过程,这个非常基础,也非常重要。
在这里插入图片描述
理解完全背包问题以后,接下来就是真的套公式了,最关键的地方还是在于如何定义状态转移方程,这个过程也比较难,需要理解题目的意思,并且清楚状态转移的条件。
在这里插入图片描述

解题代码

分析在前面已经进行介绍,这里我们逐行解释代码的作用,如果有任何疑问,欢迎后面留言。

C++ 解题代码

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {// 将字典中的单词存储到 unordered_set 中以加快查找速度unordered_set<string> wordSet(wordDict.begin(), wordDict.end());// 动态规划数组 dp,其中 dp[i] 表示 s 的前 i 个字符是否可以被拆分成字典中的单词vector<bool> dp(s.size() + 1, false);// 初始化:空字符串总是可以被拆分的dp[0] = true; // 遍历字符串 s 的每一个字符位置 ifor (int i = 1; i <= s.size(); ++i) {// 检查从 j 到 i 的子字符串 s[j:i] 是否在字典中for (int j = 0; j < i; ++j) {string target = s.substr(j, i - j);// 如果 dp[j] 为 true,且目标子串在字典中if (dp[j] && wordSet.find(target) != wordSet.end()) {// 则将 dp[i] 设为 true,表示前 i 个字符可以被拆分dp[i] = true;// 找到一个合法的拆分,跳出内层循环break;}}}// 返回 dp[s.size()],表示整个字符串 s 是否可以被拆分成字典中的单词return dp[s.size()];}
};

对应的 Java 版本为:

class Solution {public boolean wordBreak(String s, List<String> wordDict) {// 将字典中的单词存储到 HashSet 中以加快查找速度Set<String> wordSet = new HashSet<>(wordDict);// 动态规划数组 dp,其中 dp[i] 表示 s 的前 i 个字符是否可以被拆分成字典中的单词boolean[] dp = new boolean[s.length() + 1];// 初始化:空字符串总是可以被拆分的dp[0] = true;// 遍历字符串 s 的每一个字符位置 ifor (int i = 1; i <= s.length(); ++i) {// 检查从 j 到 i 的子字符串 s[j:i] 是否在字典中for (int j = 0; j < i; ++j) {String target = s.substring(j, i);// 如果 dp[j] 为 true,且目标子串在字典中if (dp[j] && wordSet.contains(target)) {// 则将 dp[i] 设为 true,表示前 i 个字符可以被拆分dp[i] = true;// 找到一个合法的拆分,跳出内层循环break;}}}// 返回 dp[s.length()],表示整个字符串 s 是否可以被拆分成字典中的单词return dp[s.length()];}
}

对应的python版本代码为:

class Solution:def wordBreak(self, s: str, wordDict: list[str]) -> bool:# 将字典中的单词存储到 set 中以加快查找速度wordSet = set(wordDict)# 动态规划数组 dp,其中 dp[i] 表示 s 的前 i 个字符是否可以被拆分成字典中的单词dp = [False] * (len(s) + 1)# 初始化:空字符串总是可以被拆分的dp[0] = True# 遍历字符串 s 的每一个字符位置 ifor i in range(1, len(s) + 1):# 检查从 j 到 i 的子字符串 s[j:i] 是否在字典中for j in range(i):target = s[j:i]# 如果 dp[j] 为 True,且目标子串在字典中if dp[j] and target in wordSet:# 则将 dp[i] 设为 True,表示前 i 个字符可以被拆分dp[i] = True# 找到一个合法的拆分,跳出内层循环break# 返回 dp[len(s)],表示整个字符串 s 是否可以被拆分成字典中的单词return dp[len(s)]

总结

本次例子中我们不再通过若干个例子介绍拆分过程,主要强调如何套公式,但是这些都是建立在对原版的完全背包问题熟悉的基础上,如果对完全背包问题不太熟悉,建议参考本博客中介绍的完全背包问题 4 步解题法,接着再套到这个题中理解。

Smileyan
2024.06.30 20:37

相关文章:

【动态规划】139. 单词拆分

139. 单词拆分 难度&#xff1a;中等 力扣地址&#xff1a;https://leetcode.cn/problems/word-break/description/ 问题描述 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意&#xff1a;不要求字…...

【C++】空指针访问成员函数

空指针访问成员函数 C中空指针也是可以调用成员函数的&#xff0c;但是也要注意有没有用到this指针 如果用到this指针&#xff0c;需要加以判断保证代码的健壮性 class Animal { public:void fun1() {//正常的成员函数}void fun2() {if (this NULL) {return;//如果没有这个…...

Linux的IO易错点总结

本文主要记录IO的一些易错操作。 阻塞IO和非阻塞IO&#xff0c;一般都是针对数据读取的&#xff0c;因为write是主动行为&#xff0c;不存在阻塞这一说。 非阻塞式IO&#xff0c;一般都要配合while轮询来读取数据。 IO多路复用 当只检测一路IO的时候&#xff0c;和普通IO的作…...

【Android面试八股文】说一说你对Android中的Context的理解吧

文章目录 一、Context是什么?1.1 主要功能和用途1.2 如何获取 Context 实例?1.3 注意事项二、Context 类的层次结构三、Context的数量四、Context的注意事项五、Android 中有多少类型的 Context,它们有什么区别 ?六、Contextlmpl实例是什么时候生成的,在 Activity 的 oncr…...

AI在音乐创作中的角色:创造还是毁灭?

目录 一、基本情况介绍 二、近期新闻 三、AI生成音乐方面的商业模式 四、人工智能和音乐人可能的合作模式 五、人们如何借助AI来创作音乐 六、人工智能在创意产业引发的伦理道德问题 七、如何平衡技术发展与提高人类创造积极性的关系&#xff1f; 总结 一、基本情况介绍…...

[深入理解DDR] 总目录

依公知及经验整理&#xff0c;原创保护&#xff0c;禁止转载。 专栏 《深入理解DDR》 蓝色的是传送门&#xff0c;点击链接即可到达指定文章。 图。 DDR 分类 导论 [RAM] DRAM 导论&#xff1a;DDR4 | DDR5 | LPDDR5 | GDRR6 | HBM 应运而生 运存与内存&#xff1f;内存与存…...

模板方法模式在金融业务中的应用及其框架实现

引言 模板方法模式&#xff08;Template Method Pattern&#xff09;是一种行为设计模式&#xff0c;它在一个方法中定义一个算法的框架&#xff0c;而将一些步骤的实现延迟到子类中。模板方法允许子类在不改变算法结构的情况下重新定义算法的某些步骤。在金融业务中&#xff…...

leetcode347.前k个高频元素

leetcode347.前k个高频元素 给你一个整数数组 nums 和一个整数 k &#xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1: 输入: nums [1,1,1,2,2,3], k 2 输出: [1,2] 示例 2: 输入: nums [1], k 1 输出: [1] 优先队列法 struct hash_…...

c++(二)

1. 类和对象 1.1. 封装 封装的意义 将属性和行为作为一个整体&#xff0c;表现生活中的事物&#xff1b;将属性和行为加以权限控制 public -> 公共权限&#xff1a;类内可以访问&#xff0c;类外也可以访问protected -> 保护权限&#xff1a;类内可以访问&#xff0c;…...

基于PHP的初中数学题库管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的初中数学题库管理系统 一 介绍 此初中数学题库管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;系统角色分为学生&#xff0c;教师和管理员。(附带参考设计文档) 技术栈&#xff1a;phpmysqlphpstudyvscode 二 功能 …...

WDG看门狗

1 WDG 1.1 简介 WDG是看门狗定时器&#xff08;Watchdog Timer&#xff09;的缩写&#xff0c;它是一种用于计算机和嵌入式系统中的定时器&#xff0c;用来检测和恢复系统故障。 看门狗就像是一个忠诚的宠物狗&#xff0c;它时刻盯着你的程序&#xff0c;确保它们正常运行。…...

zabbix server client 安装配置

Zabbix Server 采用源码包部署&#xff0c;数据库采用 MySQL8.0 版本&#xff0c;zabbix-web 使用 nginxphp 来实现。具体信息如下&#xff1a; 软件名 版本 安装方式 Zabbix Server 6.0.3 源码安装 Zabbix Agent 6.0.3 源码安装 MySQL 8.0.28 yum安装 Nginx 1.20…...

Unity关于Addressables.Release释放资源内存问题

前言 最近在编写基于Addressables的资源管理器&#xff0c;对于资源释放模块配合MemoryProfiler进行了测试&#xff0c;下面总结下测试Addressables.Release的结论。 总结 使用Addressables.Release释放资源时&#xff0c;通过MemoryProfiler检查内存信息发现加载的内容还在…...

运算放大器(运放)带宽和带宽平坦度

运算放大器带宽和带宽平坦度 电压反馈型运算放大器的带宽 下图1显示电压反馈型运算放大器的开环频率响应。有两种可能&#xff1a;图1A是最常见的情况&#xff0c;高直流增益以6dB/倍频程从极低频率下降至单位增益&#xff0c;也就是典型的单极点响应。相比之下&#xff0c;图…...

npm常用命令使用与事件案例

概述 npm&#xff08;Node Package Manager&#xff09;是一个JavaScript编程语言的包管理器&#xff0c;用于Node.js应用程序。它允许用户安装、共享和管理具有重复使用价值的代码&#xff08;包&#xff09;&#xff0c;这些代码可以是库、工具或应用程序。 npm常用命令详解…...

Spring Boot中的定时任务调度

Spring Boot中的定时任务调度 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01;今天我们将深入探讨如何在Spring Boot应用中实现定时任务调度&#xff0c;这在实际…...

Hadoop3:MapReduce中的ETL(数据清洗)

一、概念说明 “ETL&#xff0c;是英文Extract-Transform-Load的缩写&#xff0c;用来描述将数据从来源端经过抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;、加载&#xff08;Load&#xff09;至目的端的过程。ETL一词较常用在数据仓库&#…...

python解锁图片相似度的神奇力量

在这个信息爆炸的时代,图片成为了我们传递信息、表达情感和记录生活的重要方式。然而,面对海量的图片资源,如何快速准确地找到相似的图片,成为了一个亟待解决的问题。现在,让我们为您揭开图片相似度的神秘面纱,带您领略这一创新技术的魅力! 图片相似度技术,就像是一位…...

TensorFlow 的原理与使用

文章目录 TensorFlow 的基本原理1. 计算图&#xff08;Computation Graph&#xff09;2. 张量&#xff08;Tensor&#xff09;3. 会话&#xff08;Session&#xff09;4. 自动微分&#xff08;Automatic Differentiation&#xff09; TensorFlow 的使用安装 TensorFlow基本使用…...

[数据库]事务的隔离级别存储引擎

事务的隔离级别 存储引擎 举例 myisam 进行回滚操作后可以发现有一个警告没有行受到影响 memory 比如用于qq的在线离线状态...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...