当前位置: 首页 > 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的在线离线状态...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...