【动态规划】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. 单词拆分 难度:中等 力扣地址:https://leetcode.cn/problems/word-break/description/ 问题描述 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意:不要求字…...
【C++】空指针访问成员函数
空指针访问成员函数 C中空指针也是可以调用成员函数的,但是也要注意有没有用到this指针 如果用到this指针,需要加以判断保证代码的健壮性 class Animal { public:void fun1() {//正常的成员函数}void fun2() {if (this NULL) {return;//如果没有这个…...
Linux的IO易错点总结
本文主要记录IO的一些易错操作。 阻塞IO和非阻塞IO,一般都是针对数据读取的,因为write是主动行为,不存在阻塞这一说。 非阻塞式IO,一般都要配合while轮询来读取数据。 IO多路复用 当只检测一路IO的时候,和普通IO的作…...
【Android面试八股文】说一说你对Android中的Context的理解吧
文章目录 一、Context是什么?1.1 主要功能和用途1.2 如何获取 Context 实例?1.3 注意事项二、Context 类的层次结构三、Context的数量四、Context的注意事项五、Android 中有多少类型的 Context,它们有什么区别 ?六、Contextlmpl实例是什么时候生成的,在 Activity 的 oncr…...
AI在音乐创作中的角色:创造还是毁灭?
目录 一、基本情况介绍 二、近期新闻 三、AI生成音乐方面的商业模式 四、人工智能和音乐人可能的合作模式 五、人们如何借助AI来创作音乐 六、人工智能在创意产业引发的伦理道德问题 七、如何平衡技术发展与提高人类创造积极性的关系? 总结 一、基本情况介绍…...
[深入理解DDR] 总目录
依公知及经验整理,原创保护,禁止转载。 专栏 《深入理解DDR》 蓝色的是传送门,点击链接即可到达指定文章。 图。 DDR 分类 导论 [RAM] DRAM 导论:DDR4 | DDR5 | LPDDR5 | GDRR6 | HBM 应运而生 运存与内存?内存与存…...
模板方法模式在金融业务中的应用及其框架实现
引言 模板方法模式(Template Method Pattern)是一种行为设计模式,它在一个方法中定义一个算法的框架,而将一些步骤的实现延迟到子类中。模板方法允许子类在不改变算法结构的情况下重新定义算法的某些步骤。在金融业务中ÿ…...
leetcode347.前k个高频元素
leetcode347.前k个高频元素 给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 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. 封装 封装的意义 将属性和行为作为一个整体,表现生活中的事物;将属性和行为加以权限控制 public -> 公共权限:类内可以访问,类外也可以访问protected -> 保护权限:类内可以访问,…...
基于PHP的初中数学题库管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的初中数学题库管理系统 一 介绍 此初中数学题库管理系统基于原生PHP开发,数据库mysql,系统角色分为学生,教师和管理员。(附带参考设计文档) 技术栈:phpmysqlphpstudyvscode 二 功能 …...
WDG看门狗
1 WDG 1.1 简介 WDG是看门狗定时器(Watchdog Timer)的缩写,它是一种用于计算机和嵌入式系统中的定时器,用来检测和恢复系统故障。 看门狗就像是一个忠诚的宠物狗,它时刻盯着你的程序,确保它们正常运行。…...
zabbix server client 安装配置
Zabbix Server 采用源码包部署,数据库采用 MySQL8.0 版本,zabbix-web 使用 nginxphp 来实现。具体信息如下: 软件名 版本 安装方式 Zabbix Server 6.0.3 源码安装 Zabbix Agent 6.0.3 源码安装 MySQL 8.0.28 yum安装 Nginx 1.20…...
Unity关于Addressables.Release释放资源内存问题
前言 最近在编写基于Addressables的资源管理器,对于资源释放模块配合MemoryProfiler进行了测试,下面总结下测试Addressables.Release的结论。 总结 使用Addressables.Release释放资源时,通过MemoryProfiler检查内存信息发现加载的内容还在…...
运算放大器(运放)带宽和带宽平坦度
运算放大器带宽和带宽平坦度 电压反馈型运算放大器的带宽 下图1显示电压反馈型运算放大器的开环频率响应。有两种可能:图1A是最常见的情况,高直流增益以6dB/倍频程从极低频率下降至单位增益,也就是典型的单极点响应。相比之下,图…...
npm常用命令使用与事件案例
概述 npm(Node Package Manager)是一个JavaScript编程语言的包管理器,用于Node.js应用程序。它允许用户安装、共享和管理具有重复使用价值的代码(包),这些代码可以是库、工具或应用程序。 npm常用命令详解…...
Spring Boot中的定时任务调度
Spring Boot中的定时任务调度 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!今天我们将深入探讨如何在Spring Boot应用中实现定时任务调度,这在实际…...
Hadoop3:MapReduce中的ETL(数据清洗)
一、概念说明 “ETL,是英文Extract-Transform-Load的缩写,用来描述将数据从来源端经过抽取(Extract)、转换(Transform)、加载(Load)至目的端的过程。ETL一词较常用在数据仓库&#…...
python解锁图片相似度的神奇力量
在这个信息爆炸的时代,图片成为了我们传递信息、表达情感和记录生活的重要方式。然而,面对海量的图片资源,如何快速准确地找到相似的图片,成为了一个亟待解决的问题。现在,让我们为您揭开图片相似度的神秘面纱,带您领略这一创新技术的魅力! 图片相似度技术,就像是一位…...
TensorFlow 的原理与使用
文章目录 TensorFlow 的基本原理1. 计算图(Computation Graph)2. 张量(Tensor)3. 会话(Session)4. 自动微分(Automatic Differentiation) TensorFlow 的使用安装 TensorFlow基本使用…...
[数据库]事务的隔离级别存储引擎
事务的隔离级别 存储引擎 举例 myisam 进行回滚操作后可以发现有一个警告没有行受到影响 memory 比如用于qq的在线离线状态...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
