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

【划分型 DP】力扣139. 单词拆分

给你一个字符串 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 中的所有字符串 互不相同

动态规划

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordDictSet;for(auto word : wordDict){wordDictSet.insert(word);}vector<bool> dp(s.size()+1);dp[0] = true;for(int i = 1; i <= s.size(); i++){for(int j = 0; j < i; j++){if(dp[j] && wordDictSet.find(s.substr(j, i-j)) != wordDictSet.end()){dp[i] = true;break;}}}return dp[s.size()];}
};

时间复杂度:O(n^2)
空间复杂度:O(n)

这道题我们首先定义一个unordered_set来储存字典里的单词,这样有利于快速查找。然后我们定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0…i−1] 是否能被空格拆分成若干个字典中出现的单词。我们首先在外层循环遍历i,代表着遍历字符串,然后内层循环j的作用是来判断该字符串前j个字符组成的字符串能否被拆分成字典里的单词,并且判断第j+1个字符后的单词是否在字典里。这时候我们利用到了find操作,当find找不到字典里对应单词的时候,就会指向wordDictSet的end,那么只要当指针不指向end,则说明在字典里有对应单词。

最后返回dp[s.size()]即可。

相关文章:

【划分型 DP】力扣139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意&#xff1a;不要求字典中出现的单词全部都使用&#xff0c;并且字典中的单词可以重复使用。 示例 1&#xff1a; 输入: s “leetcode”, wordDic…...

Python学习从0到1 day26 第三阶段 Spark ④ 数据输出

半山腰太挤了&#xff0c;你该去山顶看看 —— 24.11.10 一、输出为python对象 1.collect算子 功能: 将RDD各个分区内的数据&#xff0c;统一收集到Driver中&#xff0c;形成一个List对象 语法&#xff1a; rdd.collect() 返回值是一个list列表 示例&#xff1a; from …...

AWTK fscript 中的 JSON 扩展函数

fscript 是 AWTK 内置的脚本引擎&#xff0c;开发者可以在 UI XML 文件中直接嵌入 fscript 脚本&#xff0c;提高开发效率。本文介绍一下 fscript 中的 ** JSON 扩展函数 ** 1.json_load 加载 json 数据。 原型 json_load(str) > object json_load(binary) > object js…...

动态规划 —— dp 问题-买卖股票的最佳时机III

1. 买卖股票的最佳时机III 题目链接&#xff1a; 123. 买卖股票的最佳时机 III - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/ 2. 题目解析 3. 算法原理 状态表示&#xff1a;以某一个位置为结尾或者…...

“绽放艺术风采、激发强国力量” 海南省第十一届中小学生艺术展演活动圆满开展

2024年11月1日&#xff0c;由省教育厅主办、琼台师范学院承办的海南省第十一届中小学生艺术展演省级展演活动在海口正式拉开帷幕。来自全省各市县、省属学校等共计4000余名师生参加本届中小学生艺术展演现场展演活动。 本届展演活动以“绽放艺术风采、激发强国力量”为主题&…...

Linux之文件和目录类命令详解(2)

Linux之文件和目录类命令详解&#xff08;2&#xff09; 1、mv-移动文件或重命名2、find-查找文件和目录3、locate-快速查找文件4、du-显示目录或文件的磁盘使用情况5、df-显示文件系统的磁盘空间使用情况6、chmod-更改文件或目录的权限7、chown-更改文件或目录的拥有者8、tree…...

NVR管理平台EasyNVR多品牌NVR管理工具/设备摄像头开启ONVIF的方法

NVR小程序接入平台EasyNVR作为一款功能强大的安防视频监控平台&#xff0c;以其出色的兼容性和灵活性&#xff0c;在智慧校园、智慧工厂、智慧水利等多个场景中得到了广泛应用。本文将重点介绍如何为大华摄像头开启ONVIF协议&#xff0c;以便与EasyNVR进行无缝对接。 大华大部分…...

Pr 视频过渡:沉浸式视频

效果面板/视频过渡/沉浸式视频 Video Transitions/Immersive Video Adobe Premiere Pro 的视频过渡效果中&#xff0c;沉浸式视频 Immersive Video效果组主要用于 VR 视频剪辑之间的过渡。 自动 VR 属性 Auto VR Properties是所有 VR 视频过渡效果的通用选项。 默认勾选&#x…...

SwiftUI开发教程系列 - 第1章:简介与环境配置

1.1 SwiftUI简介 SwiftUI 是 Apple 于 2019 年推出的声明式用户界面框架&#xff0c;旨在简化 iOS、macOS、watchOS 和 tvOS 应用的 UI 开发。与 UIKit 的命令式编程方式不同&#xff0c;SwiftUI 提供了一种声明式语法&#xff0c;让开发者可以以更加直观、简洁的方式构建 UI。…...

gitlab ci/cd搭建及使用笔记

记录下使用gitlab的ci/cd的devops构建过程中&#xff0c;一些易忘点或者踩坑点&#xff1a; 官方文档中英文&#xff08;建议英文&#xff09; https://docs.gitlab.com/ee/ci/yaml/artifacts_reports.html https://gitlab.cn/docs/jh/ci/pipelines/schedules.html为什么创建了…...

Xcode 16 中 Swift Testing 的参数化(Parameterized)机制趣谈

概述 我们之前曾在 《用接地气的例子趣谈 WWDC 24 全新的 Swift Testing 入门》系列博文以及《WWDC24&#xff08;Xcode 16&#xff09;中全新的 Swift Testing 使用进阶》博文中较为系统地介绍了今年 WWDC 24 中全新的 Swift Testing 测试系统。 不过 Swift Testing 的本领远…...

Python自动化运维DevSecOps与安全自动化

Python自动化运维DevSecOps与安全自动化 目录 &#x1f6e1;️ DevSecOps概念与实践&#x1f50d; 自动化安全扫描与漏洞修复&#x1f9f0; 基于Python的安全审计与合规性检查&#x1f433; 云平台与容器安全&#xff1a;基于Python的容器扫描工具⚠️ 自定义安全检测与漏洞修…...

2024下半年系统架构师考试【回忆版】

2024年11月10日&#xff0c;系统架构师考试如期举行&#xff0c;屡战屡败的参试倒是把北京的学校转了好几所。 本次考试时间 考试科目考试时间综合知识、案例分析8:30 - 12:30论文14:30 - 16:30 综合知识 1、1-1000以内包含5的数字个数 2、 案例分析 1、RESTful 对于前后…...

UE5.4 PCG 自定义PCG蓝图节点

ExecuteWithContext&#xff1a; PointLoopBody&#xff1a; 效果&#xff1a;点密度值与缩放成正比...

迁移学习相关基础

迁移学习 目标 将某个领域或任务上学习到的知识或模式应用到不同但相关的领域或问题中。 主要思想 从相关领域中迁移标注数据或者知识结构、完成或改进目标领域或任务的学习效果。 概述 Target data&#xff1a;和你的任务有直接关系的数据&#xff0c;但数据量少&#xff…...

华为云计算HCIE-Cloud Computing V3.0试验考试北京考场经验分享

北京试验考场 北京考场位置 1.试验考场地址 北京市海淀区北清路156号中关村环保科技示范园区M地块Q21楼 考试场选择北京&#xff0c;就是上面这个地址&#xff0c;在预约考试的时候会显示地址&#xff0c;另外在临近考试的时候也会给你发邮件&#xff0c;邮件内会提示你考试…...

数据分析——学习框架

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

量化交易系统开发-实时行情自动化交易-3.4.2.Okex行情交易数据

19年创业做过一年的量化交易但没有成功&#xff0c;作为交易系统的开发人员积累了一些经验&#xff0c;最近想重新研究交易系统&#xff0c;一边整理一边写出来一些思考供大家参考&#xff0c;也希望跟做量化的朋友有更多的交流和合作。 接下来聊聊基于Okex交易所API获取行情数…...

pytorch实现深度神经网络DNN与卷积神经网络CNN

DNN概述 深度神经网络DNN来自人脑神经元工作的原理&#xff0c;通过在计算机中逻辑抽象出多个节点&#xff0c;接收处理并向后传递信息&#xff0c;实现计算机的自我学习&#xff0c;类比结构见下图&#xff1a; 该方法通过预测输出与实际值的差异不断调整节点参数&#xff0…...

芯片测试-LDO测试

LDO测试 &#x1f4a2;LDO的简介&#x1f4a2;&#x1f4a2;压降&#x1f4a2;&#x1f4a2;决定压降的主要因素&#x1f4a2; &#x1f4a2;LDO的分类及原理&#x1f4a2;&#x1f4a2;PMOS LDO&#x1f4a2;&#x1f4a2;PMOS LDO工作过程&#x1f4a2;&#x1f4a2;PMOS LDO…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础

第三周 Day 3 &#x1f3af; 今日目标 理解类&#xff08;class&#xff09;和对象&#xff08;object&#xff09;的关系学会定义类的属性、方法和构造函数&#xff08;init&#xff09;掌握对象的创建与使用初识封装、继承和多态的基本概念&#xff08;预告&#xff09; &a…...