每天一道leetcode:139. 单词拆分(动态规划中等)
今日份题目:
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例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中的所有字符串 互不相同
题目思路
动态规划,使用和字符串相同长度的数组记录到目前为止的字符串是否能用字典表示。
状态转移方程:字符串0的位置默认是可以表示的,为true;剩下的情况,对于字符串中的每个位置,需要遍历其前边的所有字符所在的位置(a),如果某个位置(b)的dp值为true(表示这个位置b以前的字符串可以用字典表示),并且从那个位置(b)到当前位置(a)的部分字符串可以用字典中的内容表示,那么当前位置(a)就标记为true,可以表示。所以得到状态转移部分如下:
for(int i=1;i<=s.size();i++) //遍历整个字符串
{for(int j=0;j<i;j++) //遍历当前位置以前的字符,看从前边满足的位置开始到目前位置能否找到满足的情况{if(dp[j]&&word.find(s.substr(j,i-j))!=word.end()) //j往前的可以找到并且j到i也可以找到{dp[i]=true;//到i可以实现break;}}
}
代码
class Solution
{
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> word;for(int i=0;i<wordDict.size();i++) {word.insert(wordDict[i]);}bool dp[310]={false};//用来记录dp[0]=true;for(int i=1;i<=s.size();i++) //遍历整个字符串{for(int j=0;j<i;j++) //遍历当前位置以前的字符,看从前边满足的位置开始到目前位置能否找到满足的情况{if(dp[j]&&word.find(s.substr(j,i-j))!=word.end()) //j往前的可以找到并且j到i也可以找到{dp[i]=true;//到i可以实现break;}}}return dp[s.size()];//整个字符串满足条件}
};
提交结果

欢迎大家在评论区讨论,如有不懂的代码部分,欢迎在评论区留言!
相关文章:
每天一道leetcode:139. 单词拆分(动态规划中等)
今日份题目: 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 示例1 输入: s "leetcode", …...
【C++】友元(含内部类)
一、友元是什么 我把你添加为我的友元,那么你可以访问我的成员。特别注意:它是单向的。即,我把你添加为我的友元,我却不能访问你的成员,除非你把我添加为你的友元。 以下代码可以让你粗略了解友元的使用。 #includ…...
SQL | 检索数据
1-检索数据 1.1-检索单个列 SELECT prod_name FROM Products; 上述SELECT语句从Products表中检索一个名为prod_name的列。 所要查找的列在select后面,from关键字指出从那个表查询数据。 输出如下: prod_name8 inch teddy bear12 inch teddy bear18…...
typeScript 之 运算符
工具: PlayGround 算术运算符 运算符描述加-减*乘/除%取模(求余)自增–自减 注意和--,实例: let value 0; console.log(value); //0, 先显示再增加后为1 console.log(value); //2,先增加后为2再显示关系运算符 运算符描述 …...
BGP实验
题目 IP地址配置 172.16.X.0/24为模拟用户环回接口接口 172.16.7.X/32为BGP邻居关系建立的环回接口 R1: R2: R3: R4: R5: R6: R7: R8: BGP邻居关系建立、宣告和反射器、联邦配置 R…...
pytest fixture 常用参数
fixture 常用的参数 参数一:autouse,作用:自动运行,无需调用 举例一:我们在类中定义一个function 范围的fixture; 设置它自动执行autouseTrue,那么我们看下它执行结果 输出: 说明:…...
vue项目里面有多个模块的服务,前端处理url转发
先看下vue的代理配置里面: 现在是在 /pca 基础上增加了 2个模块的服务: /dca、 /api 现在服务器的nginx 没有在/pca 服务里面做转发接受 /dca、 /api的服务,所以需要前端自己去配置每个服务模块对应的 URL 先拿登录的api 做示例吧: 先定义…...
web表单
在了解了 Flask Bootstrap 基本框架之后,我们来了解一下 Flask 框架的 表单( form ),以帮助我们创建交互式的 Web 应用,最后会有个提交个人信息的例子。 Flask-WTF 是 Flask 框架的一个扩展,用来做表单的交互,是对 WT…...
C++BUG记录:文件无法创建,文件路径正确但使用了Format
问题1:xx.Format()不存在与参数列表匹配的重载函数 问题:文件的路径名字是通过Format转换组合而成的,会报错“FileName.Format()不存在与参数列表匹配的重载函数”。 FileName.Format("%s%d", FilePath, num);//报错:…...
nodejs框架 express koa介绍以及从零搭建 koa 模板
express 下载 npm install express搭建服务 const express require("express");const app express();app.get("/home", (req, res) > {res.send("home"); });app.listen(3000, () > {console.log("http://127.0.0.1:3000")…...
84 | Python可视化篇 —— Pyecharts数据可视化
文章目录 1. 简介安装和环境设置2. 基本图表类型折线图(Line Chart)散点图(Scatter Plot)柱状图(Bar Chart)饼图(Pie Chart)地理地图(Geo Map)3. 数据处理和图表配置4. 高级图表类型5. 自定义选项和交互性6. 数据可视化和动态图7. 组合图表和多子图1. 简介 Pyechart…...
【Nginx】Nginx负载均衡
负载均衡:通过反向代理来实现 Nginx的七层代理和四层代理: 七层是最常用的反向代理方式,只能配置在nginx配置文件的http模块当中 ;配置的方法名称为:upstream模块,不能写在server中也不能写在location中&a…...
vue3报错
这是因为eslint对代码的要求严格导致的,可以在package.json里面删掉"eslint:recommended",然后重启就可以正常运行了...
每日一学——IP地址和子网掩码
IP地址和子网掩码是网络中非常重要的概念。IP地址是用于标识和寻址网络中设备(如计算机、手机等)的唯一标识符。而子网掩码则用于划分网络中的子网。 IP地址是一个由32位二进制数组成的地址,通常以点分十进制的形式表示,如192.16…...
【redis 3.2 集群】
目录 一、Redis主从复制 1.概念 2.作用 2.1 数据冗余 2.2 故障恢复 2.3 负载均衡 2.4 高可用 3.缺点 4.流程 4.1 第一步 4.2 第二步 4.3 第三步 4.4 第四步 5.搭建 5.1 主 5.2 从 6.验证 二、Reids哨兵模式 1.概念 2.作用 2.1 监控 2.2 自动故障转移 2.…...
JS 解决鼠标悬浮显示弹窗 迅速离开时弹窗显示到其他位置的延迟问题
解决该问题的思路就是,判断当前鼠标的位置是否在某个div上,如果在这个div上则取消显示悬浮弹窗消息。 首先监听鼠标的移动事件 鼠标移动时判断是否在div里面进行移动了 clientX表示鼠标X的位置 client Y表示鼠标Y的位置 拿到要判断的div元素 获取off…...
树莓派命令行运行调用音频文件的函数,不报错,没有声音解决办法
树莓派接上音频首先需要切换音频不是HDMI,然后可以双击运行wav文件可以播放,但是: 命令行直接运行wav文件报错: Playing WAVE twzc.wav : Signed 16 bit Little Endian, Rate 16000 Hz, Mono命令行运行main方法也是无法播放&am…...
解决无法引入 mysql-connector-j 的问题
开发环境 Windows 10Oracle JDK 1.8Maven 3.8.8IntelliJ IDEA 2022.2.2 问题 在使用 Spring initializr 创建 Spring Boot 项目时,无法引入 mysql-connector-j 这个依赖,报错信息: com.mysql:mysql-connector-j:jar:unknown was not foun…...
解释器模式(Interpreter)
解释器模式是一种行为设计模式,可以解释语言的语法或表达式。给定一个语言,定义它的文法的一种表示,然后定义一个解释器,使用该文法来解释语言中的句子。解释器模式提供了评估语言的语法或表达式的方式。 Interpreter is a behav…...
python读入和读出图像
python提供了PIL库和opencv库对图像进行读取并保存。 图像读入读出 给定一张RGB的彩色图像,PIL库将其读入: import cv2 from PIL import Image # 读入图像 image2 Image.open(cub1.jpg) print(type(image2)) image2_array np.array(image2) print(image2_array…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...
