力扣139.单词拆分
思路:动态规划,设dp[]记录当前字符能不能通过字典里的单词到达,双层循环,外层循环遍历字符串每一个字符,内层遍历当前i字符之前的所有以i字符结尾的子串
例如字符串:leetcode
i遍历到了t
那么内层循环就会遍历:leet、eet、et、t
然后判断这些子串中有没有与字典里的单词匹配,若匹配且当前dp[j]为真,则dp[i]为真
判断dp[j] 是因为若dp[j]为真,则代表j字符可以到达,那么当前字符子串以j为起始并且字典里存在此子串,所以当前子串的结尾处也可以到达(dp[i] = true)
dp[0] 赋初值true,因为若子串起始字符为第一个字符,那么从第一个字符出发的子串当然是可以的
最后判断dp[]最后一个位置是否为真,若为真则说明此字符串可以通过字典里的单词拼凑到达最后一个字符
一开始的笨办法,虽然笨且慢,不过可能更便于理解:
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int len = s.size();auto dp = vector<bool> (len + 1); dp[0] = true; //dp[0]赋值for(int i = 1; i <= len; i++){ //外层循环遍历字符串int sw = true; //开关,若内层循环确定当前字符可到达则进行下一个字符for(int j = 0; j < i && sw; j++){ //内层循环遍历i字符前每一个以i字符结尾的子串for(auto word:wordDict){ //在字典里面找有没有此子串if(dp[j] && (word.compare(s.substr(j, i - j)) == 0)){ dp[i] = true; //如果子串存在可到达则i字符后一个字符也可到达sw = false; //如果当前字符可到达则无需继续遍历子串}}}}return dp[len];}
};
加入unordered_set之后快了很多
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int len = s.size();auto dp = vector<bool> (len + 1);dp[0] = true;auto wordset = unordered_set <string> ();for(auto word : wordDict){wordset.insert(word);}for(int i = 1; i <= len; i++){for(int j = 0; j < i; j++){if(dp[j] && wordset.find(s.substr(j, i - j)) != wordset.end()){dp[i] = true;break;}}}return dp[len];}
};
思路不变,unordered_set就是一个key为值的字典,并且unordered_set中find()若找不到对应元素,会返回.end()
相关文章:
力扣139.单词拆分
思路:动态规划,设dp[]记录当前字符能不能通过字典里的单词到达,双层循环,外层循环遍历字符串每一个字符,内层遍历当前i字符之前的所有以i字符结尾的子串 例如字符串:leetcode i遍历到了t 那么内层循环就…...
Docker 镜像命令总汇
目录 1、查看镜像列表 2、搜索镜像 3、拉取镜像 4、删除镜像 5、显示镜像详细信息 6、显示镜像历史 7、导出镜像 8、导入镜像 9、清理未使用的镜像 10、强制删除镜像 1、查看镜像列表 docker images 这个命令列出了你系统中的所有 Docker 镜像,包括镜像名…...
客户服务:助力企业抵御经济衰退的关键要素与策略
目前经济仍悬而未决是否陷入衰退。当前情况下,尽管通胀率高企,消费者支出良好,就业率也在上升,表明就业市场强劲。然而,有人认为衰退可能会在2024年第一季度发生。经济环境的不确定性可能会让人望而却步,但…...
第八周:AIPM面试准备
以下为从开始准备转行到拿到offer期间每天需要准备的10个面试题目以及相关知识补充!来源广泛,从各个地方收集,只提供题目,我自己的尝试回答也会陆续放在我的喜马拉雅,基于我粗浅的认知,分享我粗浅的作答思路…...
阿里云2核2G3M服务器能放几个网站?有限制吗?
阿里云2核2g3m服务器可以放几个网站?12个网站,阿里云服务器网的2核2G服务器上安装了12个网站,甚至还可以更多,具体放几个网站取决于网站的访客数量,像阿里云服务器网aliyunfuwuqi.com小编的网站日访问量都很少…...
Baumer工业相机堡盟工业相机如何通过NEOAPI SDK设置相机本身的数据保存(CustomData)功能(C#)
Baumer工业相机堡盟工业相机如何通过NEOAPI SDK设置相机本身的数据保存(CustomData)功能(C#) Baumer工业相机Baumer工业相机的数据保存(CustomData)功能的技术背景CameraExplorer如何使用图像剪切ÿ…...
从零开始配置kali2023环境:镜像保存和导入
对原始的镜像做了一些改动,然后把当前容器状态打包为新的镜像,这样以后可以部署到其他地方了,而不用再安装软件等改动等等 1.查看容器id ┌──(holyeyes㉿kali2023)-[~] └─$ sudo docker ps ┌──(holyeyes㉿kali2023)-[~] └─$ s…...
Transformer梳理与总结
其实transformer的成功也是源于对注意力机制的应用,其本质上还是可以归因于注意力机制,首先我们先来了解一下什么是注意力机制。在注意力机制的背景下,自主性提示被称为查询(query),给定任何查询,注意力机制…...
php之 校验多个时间段是否重复
参考网址 https://www.kancloud.cn/xiaobaoxuetp/mywork/3069416 https://segmentfault.com/a/1190000020487996 PHP判断多个时间段是否存在跨天或重复叠加的场景 /*** PHP计算两个时间段是否有交集(边界重叠不算)** param string $beginTime1 开始时间…...
atoi函数的模拟实现
这里强力推荐一篇文章 http://t.csdnimg.cn/kWuAm 详细解析了atoi函数以及其模拟实现,我这里就不说了。 这里作者先把自己模拟的代码给大家看一下。 int add(char* arr) {char* arr2 arr;while (*arr!-48){arr;}arr--;int sum 0;int n 0;while (arr ! (arr2-…...
编程笔记 html5cssjs 009 HTML链接
编程笔记 html5&css&js 009 HTML链接 一、HTML 链接二、文本链接三、图片链接四、HTML 链接- id 属性五、锚点链接六、HTML 链接 - target 属性七、属性downloadhrefpingreferrerpolicyreltargettype 八、操作小结 网页有了链接,就可根据需要进行跳转。纸质…...
Vue实现导出Excel表格,提示“文件已损坏,无法打开”的解决方法
一、vue实现导出excel 1、前端实现 xlsx是一个用于读取、解析和写入Excel文件的JavaScript库。它提供了一系列的API来处理Excel文件。使用该库,你可以将数据转换为Excel文件并下载到本地。这种方法适用于在前端直接生成Excel文件的场景。 安装xlsx依赖 npm inst…...
分发糖果,Java经典算法编程实战。
🏆作者简介,普修罗双战士,一直追求不断学习和成长,在技术的道路上持续探索和实践。 🏆多年互联网行业从业经验,历任核心研发工程师,项目技术负责人。 🎉欢迎 👍点赞✍评论…...
鸿蒙原生应用再添新丁!中国移动 入局鸿蒙
鸿蒙原生应用再添新丁!中国移动 入局鸿蒙 来自 HarmonyOS 微博1月2日消息,#中国移动APP启动鸿蒙原生应用开发#,拥有超3亿用户的中国移动APP宣布,正式基于HarmonyOS NEXT启动#鸿蒙原生应用#及元服务开发。#HarmonyOS#系统的分布式…...
一个人能不能快速搭建一套微服务环境
一、背景 大型软件系统的开发现在往往需要多人的协助,特别是前后端分离的情况下下,分工越来越细,那么一个人是否也能快速搭建一套微服务系统呢? 答案是能的。看我是怎么操作的吧。 二、搭建过程 1、首先需要一套逆向代码生成工…...
计算机毕业设计------经贸车协小程序
项目介绍 本项目分为三种用户类型,分别是租赁者,车主,管理员用户; 管理员用户包含以下功能: 管理员登录,个人中心,租赁者管理,车主管理,赛事活动管理,车类别管理,租车管理,租车订单管理,车辆出售管理,购买订单管理,…...
数据结构OJ实验11-拓扑排序与最短路径
A. DS图—图的最短路径(无框架) 题目描述 给出一个图的邻接矩阵,输入顶点v,用迪杰斯特拉算法求顶点v到其它顶点的最短路径。 输入 第一行输入t,表示有t个测试实例 第二行输入顶点数n和n个顶点信息 第三行起&…...
你的第一个JavaScript程序
JavaScript,即JS,JavaScript是一种具有函数优先的轻量级,解释型或即时编译型的编程语言。虽然它是作为开发Web页面的脚本语言而出名,但是它也被用到了很多非浏览器环境中,JavaScript基于原型编程、多范式的动态脚本语言…...
CMake入门教程【基础篇】列表操作(list)
文章目录 1. 定义列表2. 获取列表长度3. 获取列表元素4. 追加元素到列表末尾5. 插入元素到指定位置6. 移除指定位置的元素7. 移除指定值的元素8. 替换指定位置的元素9. 迭代列表元素 #mermaid-svg-IAjFPWI6IXEGYmuU {font-family:"trebuchet ms",verdana,arial,sans-…...
普中STM32-PZ6806L开发板(HAL库函数实现-读取内部温度)
简介 主芯片STM32F103ZET6,读取内部温度其他知识 内部温度所在ADC通道 温度计算公式 V25跟Avg_Slope值 参考文档 stm32f103ze.pdf 电压计算公式 Vout Vref * (D / 2^n) 其中Vref代表参考电压, n为ADC的位数, D为ADC输入的数字信号。 实现…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
