【划分型 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。 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 示例 1: 输入: s “leetcode”, wordDic…...
Python学习从0到1 day26 第三阶段 Spark ④ 数据输出
半山腰太挤了,你该去山顶看看 —— 24.11.10 一、输出为python对象 1.collect算子 功能: 将RDD各个分区内的数据,统一收集到Driver中,形成一个List对象 语法: rdd.collect() 返回值是一个list列表 示例: from …...
AWTK fscript 中的 JSON 扩展函数
fscript 是 AWTK 内置的脚本引擎,开发者可以在 UI XML 文件中直接嵌入 fscript 脚本,提高开发效率。本文介绍一下 fscript 中的 ** JSON 扩展函数 ** 1.json_load 加载 json 数据。 原型 json_load(str) > object json_load(binary) > object js…...
动态规划 —— dp 问题-买卖股票的最佳时机III
1. 买卖股票的最佳时机III 题目链接: 123. 买卖股票的最佳时机 III - 力扣(LeetCode)https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/ 2. 题目解析 3. 算法原理 状态表示:以某一个位置为结尾或者…...
“绽放艺术风采、激发强国力量” 海南省第十一届中小学生艺术展演活动圆满开展
2024年11月1日,由省教育厅主办、琼台师范学院承办的海南省第十一届中小学生艺术展演省级展演活动在海口正式拉开帷幕。来自全省各市县、省属学校等共计4000余名师生参加本届中小学生艺术展演现场展演活动。 本届展演活动以“绽放艺术风采、激发强国力量”为主题&…...
Linux之文件和目录类命令详解(2)
Linux之文件和目录类命令详解(2) 1、mv-移动文件或重命名2、find-查找文件和目录3、locate-快速查找文件4、du-显示目录或文件的磁盘使用情况5、df-显示文件系统的磁盘空间使用情况6、chmod-更改文件或目录的权限7、chown-更改文件或目录的拥有者8、tree…...
NVR管理平台EasyNVR多品牌NVR管理工具/设备摄像头开启ONVIF的方法
NVR小程序接入平台EasyNVR作为一款功能强大的安防视频监控平台,以其出色的兼容性和灵活性,在智慧校园、智慧工厂、智慧水利等多个场景中得到了广泛应用。本文将重点介绍如何为大华摄像头开启ONVIF协议,以便与EasyNVR进行无缝对接。 大华大部分…...
Pr 视频过渡:沉浸式视频
效果面板/视频过渡/沉浸式视频 Video Transitions/Immersive Video Adobe Premiere Pro 的视频过渡效果中,沉浸式视频 Immersive Video效果组主要用于 VR 视频剪辑之间的过渡。 自动 VR 属性 Auto VR Properties是所有 VR 视频过渡效果的通用选项。 默认勾选&#x…...
SwiftUI开发教程系列 - 第1章:简介与环境配置
1.1 SwiftUI简介 SwiftUI 是 Apple 于 2019 年推出的声明式用户界面框架,旨在简化 iOS、macOS、watchOS 和 tvOS 应用的 UI 开发。与 UIKit 的命令式编程方式不同,SwiftUI 提供了一种声明式语法,让开发者可以以更加直观、简洁的方式构建 UI。…...
gitlab ci/cd搭建及使用笔记
记录下使用gitlab的ci/cd的devops构建过程中,一些易忘点或者踩坑点: 官方文档中英文(建议英文) 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(Xcode 16)中全新的 Swift Testing 使用进阶》博文中较为系统地介绍了今年 WWDC 24 中全新的 Swift Testing 测试系统。 不过 Swift Testing 的本领远…...
Python自动化运维DevSecOps与安全自动化
Python自动化运维DevSecOps与安全自动化 目录 🛡️ DevSecOps概念与实践🔍 自动化安全扫描与漏洞修复🧰 基于Python的安全审计与合规性检查🐳 云平台与容器安全:基于Python的容器扫描工具⚠️ 自定义安全检测与漏洞修…...
2024下半年系统架构师考试【回忆版】
2024年11月10日,系统架构师考试如期举行,屡战屡败的参试倒是把北京的学校转了好几所。 本次考试时间 考试科目考试时间综合知识、案例分析8:30 - 12:30论文14:30 - 16:30 综合知识 1、1-1000以内包含5的数字个数 2、 案例分析 1、RESTful 对于前后…...
UE5.4 PCG 自定义PCG蓝图节点
ExecuteWithContext: PointLoopBody: 效果:点密度值与缩放成正比...
迁移学习相关基础
迁移学习 目标 将某个领域或任务上学习到的知识或模式应用到不同但相关的领域或问题中。 主要思想 从相关领域中迁移标注数据或者知识结构、完成或改进目标领域或任务的学习效果。 概述 Target data:和你的任务有直接关系的数据,但数据量少ÿ…...
华为云计算HCIE-Cloud Computing V3.0试验考试北京考场经验分享
北京试验考场 北京考场位置 1.试验考场地址 北京市海淀区北清路156号中关村环保科技示范园区M地块Q21楼 考试场选择北京,就是上面这个地址,在预约考试的时候会显示地址,另外在临近考试的时候也会给你发邮件,邮件内会提示你考试…...
数据分析——学习框架
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...
量化交易系统开发-实时行情自动化交易-3.4.2.Okex行情交易数据
19年创业做过一年的量化交易但没有成功,作为交易系统的开发人员积累了一些经验,最近想重新研究交易系统,一边整理一边写出来一些思考供大家参考,也希望跟做量化的朋友有更多的交流和合作。 接下来聊聊基于Okex交易所API获取行情数…...
pytorch实现深度神经网络DNN与卷积神经网络CNN
DNN概述 深度神经网络DNN来自人脑神经元工作的原理,通过在计算机中逻辑抽象出多个节点,接收处理并向后传递信息,实现计算机的自我学习,类比结构见下图: 该方法通过预测输出与实际值的差异不断调整节点参数࿰…...
芯片测试-LDO测试
LDO测试 💢LDO的简介💢💢压降💢💢决定压降的主要因素💢 💢LDO的分类及原理💢💢PMOS LDO💢💢PMOS LDO工作过程💢💢PMOS LDO…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]
报错信息:libc.so.6: cannot open shared object file: No such file or directory: #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...
