day39|139.单词拆分 背包问题ending
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、确定dp数组以及下标的含义
dp[j]:拆分字符串的长度为j,dp[j]=true表示可以拆分为一个或多个字典中出现的单词。
2、确定递推公式
完全背包,重复利用物品,且为排列数
字符串为背包,单词为物品,截字符串(j-len,j)看是否是一个单词,并且他的前序子串也是一个或多个单词,也就是判断是否为true
所以递推公式为:
if(j>=len&&dp[j-len]&&word.equals(s.substring(j-len,j)))就为true
3、dp数组初始化
初始化dp[0]=true,否则所有都为false
4、确定遍历顺序
本题要求是排列数,有顺序要求
5、打印dp数组
class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp=new boolean[s.length()+1];//有空字符串dp[0]=true;for (int j=1;j<=s.length();j++){for (String word:wordDict){int len=word.length();if (j>=len&&dp[j-len]&&word.equals(s.substring(j-len,j))){dp[j]=true;break;}}}/* for (int j=1;j<=s.length();j++){System.out.print(dp[j]+" ");}*/return dp[s.length()];}
}
相关文章:
day39|139.单词拆分 背包问题ending
139.单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 示例 1: 输入: s "leetcode",…...
Shell脚本编程
Shell编程 视频地址https://www.bilibili.com/video/BV1hW41167NW/?p1&vd_source977d52a6b92ce8b6ae67c16fc61f0428 第一章 Shell概述 大数据程序员为什么要学习Shell呢? 需要看懂运维人员编写的Shell程序偶尔会编写一些简单的Shell程序来管理集群…...
ChatGPT解答:JavaScript保存当前网页页面图片为pdf文件或者word文件,前端用vue2,给出详细的方案和代码
ChatGPT解答:JavaScript保存当前网页页面图片为pdf文件或者word文件,前端用vue2,给出详细的方案和代码 ChatGPTDemo Based on OpenAI API (gpt-3.5-turbo). JavaScript保存当前网页页面图片为pdf文件或者word文件,前端用vue2&am…...
Python基础学习11——文件
我们可以利用python对本电脑文件夹里的文件进行处理,python中提供了一系列相关的方法和函数供我们使用。 读取文件 我们现在在本python文件中有一个txt文件名为Lego,那么我们就可以利用python打开该文件 with open(Lego.txt) as file_text:contents …...
外网用户打不开公司的网站?web服务器端口映射到公网
我们经常会遇到这样的情景,在公司内部可以打开公司的网站,在家里或者外网却打不开,按照网上的做法,重新启动了服务器和iis,还是不行。许多用户设置了路由器端口映射功能,但是端口映射不成功怎么办ÿ…...
【CS224W】(task9)图神经网络的表示能力(更新中!!)
note 基于图同构网络(GIN)的图表征网络。为了得到图表征首先需要做节点表征,然后做图读出。GIN中节点表征的计算遵循WL Test算法中节点标签的更新方法,因此它的上界是WL Test算法。 在图读出中,我们对所有的节点表征&…...
binlog找回误删数据
1、检查当前是否开启binlog存储 输入命令show variables like %log_bin%;,结果如下 可以看到log_bin的值是ON,说明binlog开启了。 2、查找binlog的存储位置 这个去到数据库的my.cnf配置文件中寻找,有一个log_bin的配置 切换到log_bin的目…...
《程序员面试金典(第6版)》面试题 02.03. 删除中间节点
题目描述 若链表中的某个节点,既不是链表头节点,也不是链表尾节点,则称其为该链表的「中间节点」。 假定已知链表的某一个中间节点,请实现一种算法,将该节点从链表中删除。 例如: 传入节点 c(…...
Spring Boot
目录 SpringBoot SpringBoot创建和使用 什么是Spring Boot Spring Boot优点 Spring Boot项目的创建 项目目录介绍和运行 目录介绍 项目运行 SpringBoot核心设计思想 SpringBoot的配置文件 配置文件的作用 配置文件的格式 注意事项 properties配置文件 propertie…...
图论初入门
目录 一、前言 二、图的概念 三、例题及相关概念 1、全球变暖(2018年省赛,lanqiao0J题号178) 2、欧拉路径 3、小例题 4、例题(洛谷P7771) 一、前言 本文主要讲了树与图的基本概念,图的存储、DFS遍历…...
02-Oracle数据库的启动与关闭
本文章主要讲解Oracle数据库的启动与关闭方法,详细讲解启动Oracle的命令,三种启动数据库的方法及区别;关闭数据库的4种方法及他们的区别。 启动和关闭数据库 •数据库没启动前,只有拥有DBA权限或者以sysoper或sysdba身份才能连接到…...
网络营销培训完能达到什么水平?学完能创业吗?
网络营销本身就是一门创业的技术,很多人学习网络营销,往往担心学完以后技术达不到,再工作几年才可以创业,实际这是错误的理解,那么,网络营销培训完能达到什么水平?新手学员参加网络营销培训&…...
大数据技术之——zeppelin数据清洗
一、zeppelin的安装zeppelin解压后进入到conf配置文件界面。修改zeppelin-site.xml[roothadoop02 conf]# cp zeppelin-site.xml.template zeppelin-site.xml[roothadoop02 conf]# vim zeppelin-site.xml将IP地址和端口号设置成自己的修改 zeppelin-env.shexport JAVA HOME/opt/…...
Barra模型因子的构建及应用系列五之NonLinear Size因子
一、摘要 在前期的Barra模型系列文章中,我们构建了Size因子、Beta因子、Momentum因子和Residual Volatility因子,并分别创建了对应的单因子策略,本节文章在该系列下进一步构建NonLinear Size因子。从回测结果看,自2022年以来&…...
C++ 常用命令行开发工具(Linux)
文章目录1、简介2、gcc / g2.1 system(执行shell 命令)2.2 popen(建立管道I/O)2.3 vforkexec(新建子进程)3、clang3.1 下载和安装clang3.2 clang和gcc比较3.2.1 gcc3.2.2 clang3.2.3 LLVM4、make4.1 例子14…...
java基础学习 day47(抽象类,抽象方法)
1. 抽象方法 将共性的行为(方法)抽取到父类之后,由于每一个子类执行的内容是不一样的,所以,在父类中不能确定具体的方法体,该方法就可以定义为抽象方法。抽象方法定义格式: public abstract 返…...
Java代码弱点与修复之——Open redirect(开放重定向)
弱点描述 Open redirect , 开放重定向,是一种常见的安全漏洞,也被称为“重定向漏洞”。该漏洞通常出现在 Web 应用程序中,攻击者可以利用它将用户重定向到恶意站点,从而进行钓鱼攻击、恶意软件传播、诱骗等活动。 在 Java 中,通过重定向 HTTP 请求来实现应用程序中的跳转…...
Go 指针
指针在编程中,一个内存地址用来定位一段内存。通常地,一个内存地址用一个操作系统原生字(native word)来存储。 一个原生字在32位操作系统上占4个字节,在64位操作系统上占8个字节。 所以,32位操作系统上的理…...
shardingsphere5.1.1分表分库yaml配置 自定义策略
前言通过阅读官方稳定给出示例 https://shardingsphere.apache.org/document一、基本配置示例spring:sharding:datasource:names: ds0, ds1ds0:driver-class-name: com.mysql.jdbc.Driverurl: jdbc:mysql://localhost:3306/db0username: rootpassword: rootds1:driver-class-na…...
“探索未来:VR全景直播技术引领新媒体时代”
随着虚拟现实技术的不断发展,VR全景直播已经成为了越来越受欢迎的直播形式。VR全景直播可以让观众通过虚拟现实设备亲临直播现场,享受身临其境的观看体验。VR全景直播是什么? VR全景直播是虚拟现实技术和直播的结合。相对于传统直播ÿ…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
